Submission #2599679
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define int ll
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))
using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<","<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"{";
REP(i,(int)v.size()){
if(i)os<<",";
os<<v[i];
}
os<<"}";
return os;
}
ll read(){
ll i;
scanf("%" SCNd64,&i);
return i;
}
void printSpace(){
printf(" ");
}
void printEoln(){
printf("\n");
}
void print(ll x,int suc=1){
printf("%" PRId64,x);
if(suc==1)
printEoln();
if(suc==2)
printSpace();
}
string readString(){
static char buf[3341000];
scanf("%s",buf);
return string(buf);
}
char* readCharArray(){
static char buf[3341000];
static int bufUsed=0;
char* ret=buf+bufUsed;
scanf("%s",ret);
bufUsed+=strlen(ret)+1;
return ret;
}
template<class T,class U>
void chmax(T& a,U b){
if(a<b)
a=b;
}
template<class T,class U>
void chmin(T& a,U b){
if(b<a)
a=b;
}
template<class T>
T Sq(const T& t){
return t*t;
}
#define CAPITAL
void Yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<endl;
#else
cout<<"Yes"<<endl;
#endif
if(ex)exit(0);
}
void No(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<endl;
#else
cout<<"No"<<endl;
#endif
if(ex)exit(0);
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
int d;
/*
struct SegTree{
vi pos,cnt,lt,rt,sm;
int s;
SegTree(vi xs){
int n=xs.size();
s=1;
while(s<n)s*=2;
pos=xs;
cnt.resize(s,0);
lt.resize(s*2,-1);
rt.resize(s*2,-1);
sm.resize(s*2,0);
}
void UpdateNode(int i){
sm[i]=sm[i*2]+sm[i*2+1];
int a=rt[i*2],b=lt[i*2+1];
if(a!=-1&&b!=-1&&b-a-1<=d)
sm[i]+=b-a-1;
lt[i]=(lt[i*2]!=-1?lt[i*2],lt[i*2+1]);
rt[i]=(rt[i*2+1]!=-1?rt[i*2+1],rt[i*2]);
}
void Update(int i,int v){
cnt[i]+=v;
bool cur=cnt[i];
int pos=pos[i];
i+=s;
if(cur){
lt[i]=rt[i]=pos[i];
sum[i]=1;
}else{
lt[i]=rt[i]=-1;
sum[i]=0;
}
while((i>>=1))
UpdateNode(i);
}
int Get(){
return sm[1];
}
};
* */
struct SegTree{
vi pos;
int Rng(int a,int b){
a=pos[a];
b=pos[b];
if(b-a-1<=d)return b-a-1;
else return 0;
}
int ans;
multiset<signed> s;
SegTree(vi xs){
pos=xs;
ans=0;
}
void Update(signed i,int v){
if(v==1){
auto itr=s.lower_bound(i);
int a=-1,b=-1;
if(itr!=s.end()){
b=*itr;
if(i==b){
s.insert(itr,i);
return;
}
}
if(itr!=s.begin()){
itr--;
a=*itr;
itr++;
}
if(a!=-1&&b!=-1)
ans-=Rng(a,b);
ans++;
if(a!=-1)
ans+=Rng(a,i);
if(b!=-1)
ans+=Rng(i,b);
s.insert(itr,i);
}else{
auto itr=s.lower_bound(i);
itr=s.erase(itr);
int a=-1,b=-1;
if(itr!=s.end()){
b=*itr;
if(b==i)return;
ans-=Rng(i,b);
}
if(itr!=s.begin()){
itr--;
a=*itr;
ans-=Rng(a,i);
}
ans--;
if(a!=-1&&b!=-1)
ans+=Rng(a,b);
}
}
int Get(){
return ans;
}
};
signed main(){
int y=read(),w=read();
int n=read(),m=read();
d=read();
vi a(n);
REP(i,n)
a[i]=read()-1;
vector<vi> waf(w);
REP(i,m){
int b=read()-1,c=read()-1;
waf[c].PB(b);
}
vi pos;
REP(i,w)for(auto x:a)
pos.PB(i+x);
REP(i,w)for(auto x:waf[i]){
pos.PB(x*w+i);
pos.PB((x+1)*w+i);
}
sort(ALL(pos));
pos.erase(unique(ALL(pos)),pos.end());
SegTree seg(pos);
REP(i,w)for(auto x:waf[i]){
int j=lower_bound(ALL(pos),x*w+i)-pos.begin();
seg.Update(j,1);
}
vi ans(w);
REP(i,w){
for(auto x:a){
int j=lower_bound(ALL(pos),x+i)-pos.begin();
seg.Update(j,1);
}
ans[i]=seg.Get();
for(auto x:a){
int j=lower_bound(ALL(pos),x+i)-pos.begin();
seg.Update(j,-1);
}
for(auto x:waf[i]){
{
int j=lower_bound(ALL(pos),x*w+i)-pos.begin();
seg.Update(j,-1);
}
{
int j=lower_bound(ALL(pos),(x+1)*w+i)-pos.begin();
seg.Update(j,1);
}
}
}
REP(i,w)
print(ans[i]);
}
Submission Info
Submission Time
2018-06-02 21:37:57+0900
Task
E - 祝日
User
maroonrk
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
4968 Byte
Status
AC
Exec Time
3950 ms
Memory
128092 KB
Compile Error
./Main.cpp: In function ‘ll read()’:
./Main.cpp:55:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%" SCNd64,&i);
^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:77:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",buf);
^
./Main.cpp: In function ‘char* readCharArray()’:
./Main.cpp:85:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",ret);
^
Judge Result
Set Name
Sample
Subtask1
All
Score / Max Score
0 / 0
600 / 600
100 / 100
Status
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
200 ms
15316 KB
01-02.txt
AC
202 ms
12628 KB
01-03.txt
AC
106 ms
9588 KB
01-04.txt
AC
34 ms
3484 KB
01-05.txt
AC
192 ms
9688 KB
01-06.txt
AC
186 ms
9044 KB
01-07.txt
AC
174 ms
8868 KB
01-08.txt
AC
25 ms
3720 KB
01-09.txt
AC
218 ms
12252 KB
01-10.txt
AC
27 ms
2828 KB
01-11.txt
AC
129 ms
12632 KB
01-12.txt
AC
138 ms
11476 KB
01-13.txt
AC
153 ms
13312 KB
01-14.txt
AC
55 ms
5296 KB
01-15.txt
AC
192 ms
10328 KB
01-16.txt
AC
5 ms
1536 KB
01-17.txt
AC
36 ms
2684 KB
01-18.txt
AC
216 ms
8996 KB
01-19.txt
AC
213 ms
14808 KB
01-20.txt
AC
212 ms
13016 KB
02-01.txt
AC
3895 ms
128092 KB
02-02.txt
AC
1021 ms
33764 KB
02-03.txt
AC
992 ms
38116 KB
02-04.txt
AC
1411 ms
39016 KB
02-05.txt
AC
3642 ms
123868 KB
02-06.txt
AC
1769 ms
58980 KB
02-07.txt
AC
174 ms
8888 KB
02-08.txt
AC
281 ms
10732 KB
02-09.txt
AC
2350 ms
108256 KB
02-10.txt
AC
138 ms
5364 KB
02-11.txt
AC
2353 ms
100576 KB
02-12.txt
AC
499 ms
17000 KB
02-13.txt
AC
800 ms
32996 KB
02-14.txt
AC
131 ms
7276 KB
02-15.txt
AC
785 ms
24940 KB
02-16.txt
AC
69 ms
4592 KB
02-17.txt
AC
66 ms
3064 KB
02-18.txt
AC
278 ms
9712 KB
02-19.txt
AC
3950 ms
127072 KB
02-20.txt
AC
175 ms
8788 KB
02-21.txt
AC
1155 ms
66148 KB
02-22.txt
AC
2 ms
256 KB
02-23.txt
AC
3453 ms
71392 KB
02-24.txt
AC
1792 ms
36324 KB
02-25.txt
AC
1299 ms
24040 KB
02-26.txt
AC
3 ms
384 KB
02-27.txt
AC
261 ms
10864 KB
02-28.txt
AC
906 ms
34280 KB
02-29.txt
AC
184 ms
8176 KB
02-30.txt
AC
189 ms
8316 KB
02-31.txt
AC
193 ms
8316 KB
02-32.txt
AC
644 ms
21348 KB
sample-01.txt
AC
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB
sample-03.txt
AC
1 ms
256 KB
sample-04.txt
AC
1 ms
256 KB