Submission #2600015
Source Code Expand
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<array> #include<map> #include<iomanip> #include<assert.h> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase //cout<<setprecision(20) //cin.tie(0); //ios::sync_with_stdio(false); const llint mod=1000000007; const llint big=2.19e15+1; const long double pai=3.141592653589793238462643383279502884197; const long double eps=1e-15; template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){return a/gcd(a,b)*b;} template<class T> void SO(T& ve){sort(ve.begin(),ve.end());} template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());} llint LBI(vector<llint>&ar,llint in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();} llint UBI(vector<llint>&ar,llint in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();} int main(void){ //祝日追加クエリを解けばよい llint y,w,n,m,d,i,j;cin>>y>>w>>n>>m>>d; vector<llint>A(n); vector<vector<llint>>B(w); for(i=0;i<n;i++){cin>>A[i];A[i]--;} for(i=0;i<m;i++){ llint b,c;cin>>b>>c;b--;c--; B[c].pub(b); } multiset<llint>syu; syu.ins(-big);syu.ins(big); llint ans=0; for(i=0;i<w;i++){ for(auto it:B[i]){ llint in=it*w+i; llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans++; if(in-mae-1<=d){ans+=in-mae-1;} if(ato-in-1<=d){ans+=ato-in-1;} if(ato-mae-1<=d){ans-=ato-mae-1;} } syu.ins(in); } } for(auto it:A){ llint in=it; llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans++; if(in-mae-1<=d){ans+=in-mae-1;} if(ato-in-1<=d){ans+=ato-in-1;} if(ato-mae-1<=d){ans-=ato-mae-1;} } syu.ins(in); } for(i=0;i<w;i++){ cout<<ans<<endl; for(auto it:B[i]){ llint in=it*w+i; syu.era(syu.lower_bound(in));//一つだけけす llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans--; if(in-mae-1<=d){ans-=in-mae-1;} if(ato-in-1<=d){ans-=ato-in-1;} if(ato-mae-1<=d){ans+=ato-mae-1;} } } for(auto it:B[i]){ llint in=(it+1)*w+i; llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans++; if(in-mae-1<=d){ans+=in-mae-1;} if(ato-in-1<=d){ans+=ato-in-1;} if(ato-mae-1<=d){ans-=ato-mae-1;} } syu.ins(in); } for(auto it:A){ llint in=it+i; syu.era(syu.lower_bound(in));//一つだけけす llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans--; if(in-mae-1<=d){ans-=in-mae-1;} if(ato-in-1<=d){ans-=ato-in-1;} if(ato-mae-1<=d){ans+=ato-mae-1;} } } for(auto it:A){ llint in=it+1+i; llint mae=*prev(syu.upper_bound(in)); llint ato=*syu.lower_bound(in); if(mae!=in&&in!=ato){ ans++; if(in-mae-1<=d){ans+=in-mae-1;} if(ato-in-1<=d){ans+=ato-in-1;} if(ato-mae-1<=d){ans-=ato-mae-1;} } syu.ins(in); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 祝日 |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 3717 Byte |
Status | AC |
Exec Time | 3774 ms |
Memory | 12160 KB |
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 | 385 ms | 10880 KB |
01-02.txt | AC | 324 ms | 8960 KB |
01-03.txt | AC | 233 ms | 6912 KB |
01-04.txt | AC | 64 ms | 2560 KB |
01-05.txt | AC | 232 ms | 6528 KB |
01-06.txt | AC | 216 ms | 6016 KB |
01-07.txt | AC | 199 ms | 5704 KB |
01-08.txt | AC | 67 ms | 2816 KB |
01-09.txt | AC | 311 ms | 8704 KB |
01-10.txt | AC | 52 ms | 2048 KB |
01-11.txt | AC | 249 ms | 8960 KB |
01-12.txt | AC | 208 ms | 8064 KB |
01-13.txt | AC | 307 ms | 9600 KB |
01-14.txt | AC | 85 ms | 3712 KB |
01-15.txt | AC | 252 ms | 7040 KB |
01-16.txt | AC | 57 ms | 1152 KB |
01-17.txt | AC | 38 ms | 1920 KB |
01-18.txt | AC | 209 ms | 6016 KB |
01-19.txt | AC | 391 ms | 10880 KB |
01-20.txt | AC | 334 ms | 9344 KB |
02-01.txt | AC | 2349 ms | 10880 KB |
02-02.txt | AC | 717 ms | 7296 KB |
02-03.txt | AC | 738 ms | 11152 KB |
02-04.txt | AC | 1347 ms | 9984 KB |
02-05.txt | AC | 2217 ms | 10624 KB |
02-06.txt | AC | 1158 ms | 7936 KB |
02-07.txt | AC | 201 ms | 5724 KB |
02-08.txt | AC | 331 ms | 1408 KB |
02-09.txt | AC | 1391 ms | 11520 KB |
02-10.txt | AC | 109 ms | 1792 KB |
02-11.txt | AC | 1768 ms | 9984 KB |
02-12.txt | AC | 456 ms | 7424 KB |
02-13.txt | AC | 617 ms | 7040 KB |
02-14.txt | AC | 106 ms | 1408 KB |
02-15.txt | AC | 556 ms | 6912 KB |
02-16.txt | AC | 26 ms | 384 KB |
02-17.txt | AC | 76 ms | 1920 KB |
02-18.txt | AC | 252 ms | 6016 KB |
02-19.txt | AC | 1992 ms | 12160 KB |
02-20.txt | AC | 189 ms | 5748 KB |
02-21.txt | AC | 389 ms | 2304 KB |
02-22.txt | AC | 2 ms | 256 KB |
02-23.txt | AC | 3774 ms | 11008 KB |
02-24.txt | AC | 2027 ms | 8064 KB |
02-25.txt | AC | 1308 ms | 7424 KB |
02-26.txt | AC | 2 ms | 256 KB |
02-27.txt | AC | 95 ms | 640 KB |
02-28.txt | AC | 363 ms | 1664 KB |
02-29.txt | AC | 191 ms | 5760 KB |
02-30.txt | AC | 201 ms | 5760 KB |
02-31.txt | AC | 202 ms | 5760 KB |
02-32.txt | AC | 231 ms | 1280 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 |