Submission #2601748


Source Code Expand

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-10;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
int p[110000];
int q[110000];
long long t[110000];
long long ans[110000];
long long ret;
vector<int>g[110000];
set<pair<long long,int> > S;
long long d;
void DEL(long long a,int b){
	set<pair<long long,int> >::iterator it=S.lower_bound(make_pair(a,b));
	int same=0;
	long long dif1=0;
	long long dif2=0;
	if(it!=S.begin()){
		it--;
		dif1=a-(*it).first;
		if(dif1==0)same=1;
		it++;
	}else dif1=inf;
	it++;
	if(it!=S.end()){
		dif2=(*it).first-a;
		if(dif2==0)same=1;
	}else dif2=inf;
	if(1<=dif1-1&&dif1-1<=d)ret-=(dif1-1);
	if(1<=dif2-1&&dif2-1<=d)ret-=(dif2-1);
	if(1<=dif1+dif2-1&&dif1+dif2-1<=d)ret+=(dif1+dif2-1);
	if(!same)ret--;
	S.erase(make_pair(a,b));
}
void ADD(long long a,int b){
	set<pair<long long,int> >::iterator it=S.lower_bound(make_pair(a,b));
	int same=0;
	long long dif1=0;
	long long dif2=0;
	if(it!=S.begin()){
		it--;
		dif1=a-(*it).first;
		if(dif1==0)same=1;
		it++;
	}else dif1=inf;
	if(it!=S.end()){
		dif2=(*it).first-a;
		if(dif2==0)same=1;
	}else dif2=inf;
	if(1<=dif1-1&&dif1-1<=d)ret+=(dif1-1);
	if(1<=dif2-1&&dif2-1<=d)ret+=(dif2-1);
	if(1<=dif1+dif2-1&&dif1+dif2-1<=d)ret-=(dif1+dif2-1);
	if(!same)ret++;
	S.insert(make_pair(a,b));
}
int main(){
	int a,b;
	int n,m;
	scanf("%d%d%d%d%lld",&a,&b,&n,&m,&d);
	for(int i=0;i<n;i++){
		scanf("%lld",t+i);t[i]--;
	}
	for(int i=0;i<m;i++){
		scanf("%d%d",p+i,q+i);p[i]--;q[i]--;
		g[q[i]].push_back(i);
	}
	
	for(int i=0;i<n;i++){
		S.insert(make_pair(t[i],-1));
	}
	for(int i=0;i<m;i++){
		S.insert(make_pair((long long)p[i]*b+q[i],q[i]));
	}
	ret=0;
	long long last=-1;
	for(set<pair<long long,int> >::iterator it=S.begin();it!=S.end();it++){
		if(last!=(*it).first){
			ret++;
			if(last!=-1){
				if((*it).first-last-1<=d)ret+=(*it).first-last-1;
			}
			last=(*it).first;

		}
	}
	ans[0]=ret;
	for(int i=0;i<b-1;i++){
		for(int j=0;j<n;j++){
			DEL(t[j]+i,-1);
		}
		for(int j=0;j<n;j++){
			ADD(t[j]+i+1,-1);
		}
		
		for(int j=0;j<g[i].size();j++){
			int at=g[i][j];
			long long day=(long long)p[at]*b+q[at];
			DEL(day,i);
		}
		for(int j=0;j<g[i].size();j++){
			int at=g[i][j];
			long long day=(long long)p[at]*b+q[at];
			ADD(day+b,i);
		}
		//for(set<pair<long long,int> >::iterator it=S.begin();it!=S.end();it++){
		//	printf("%lld ",(*it).first);
		//}
		//printf("\n");
		ans[i+1]=ret;
	}
	for(int i=0;i<b;i++)printf("%lld\n",ans[i]);
}

Submission Info

Submission Time
Task E - 祝日
User tozangezan
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3043 Byte
Status AC
Exec Time 3545 ms
Memory 15104 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:80:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%lld",&a,&b,&n,&m,&d);
                                      ^
./Main.cpp:82:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",t+i);t[i]--;
                    ^
./Main.cpp:85:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",p+i,q+i);p[i]--;q[i]--;
                        ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 600 / 600 100 / 100
Status
AC × 4
AC × 22
AC × 56
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, sample-01.txt, sample-02.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 166 ms 14848 KB
01-02.txt AC 154 ms 13824 KB
01-03.txt AC 101 ms 12032 KB
01-04.txt AC 31 ms 6912 KB
01-05.txt AC 152 ms 12160 KB
01-06.txt AC 159 ms 11904 KB
01-07.txt AC 100 ms 11748 KB
01-08.txt AC 23 ms 6784 KB
01-09.txt AC 204 ms 13440 KB
01-10.txt AC 25 ms 6400 KB
01-11.txt AC 133 ms 13952 KB
01-12.txt AC 138 ms 13056 KB
01-13.txt AC 163 ms 13824 KB
01-14.txt AC 52 ms 8320 KB
01-15.txt AC 155 ms 12544 KB
01-16.txt AC 5 ms 4352 KB
01-17.txt AC 38 ms 6656 KB
01-18.txt AC 179 ms 11904 KB
01-19.txt AC 166 ms 14848 KB
01-20.txt AC 152 ms 13952 KB
02-01.txt AC 2042 ms 14848 KB
02-02.txt AC 624 ms 12672 KB
02-03.txt AC 648 ms 14080 KB
02-04.txt AC 1122 ms 14336 KB
02-05.txt AC 2081 ms 14720 KB
02-06.txt AC 1031 ms 12928 KB
02-07.txt AC 104 ms 11788 KB
02-08.txt AC 274 ms 5504 KB
02-09.txt AC 1334 ms 13824 KB
02-10.txt AC 92 ms 6144 KB
02-11.txt AC 1383 ms 14592 KB
02-12.txt AC 452 ms 12672 KB
02-13.txt AC 605 ms 12544 KB
02-14.txt AC 95 ms 5504 KB
02-15.txt AC 547 ms 12416 KB
02-16.txt AC 27 ms 4352 KB
02-17.txt AC 68 ms 6656 KB
02-18.txt AC 233 ms 11904 KB
02-19.txt AC 2096 ms 14848 KB
02-20.txt AC 56 ms 11768 KB
02-21.txt AC 385 ms 5120 KB
02-22.txt AC 3 ms 4352 KB
02-23.txt AC 3545 ms 15104 KB
02-24.txt AC 1886 ms 13312 KB
02-25.txt AC 1160 ms 12672 KB
02-26.txt AC 4 ms 4352 KB
02-27.txt AC 97 ms 4480 KB
02-28.txt AC 384 ms 4736 KB
02-29.txt AC 178 ms 11776 KB
02-30.txt AC 185 ms 11776 KB
02-31.txt AC 187 ms 11776 KB
02-32.txt AC 226 ms 4608 KB
sample-01.txt AC 3 ms 4352 KB
sample-02.txt AC 3 ms 4352 KB
sample-03.txt AC 3 ms 4352 KB
sample-04.txt AC 3 ms 4352 KB