Submission #2600569
Source Code Expand
#define DEB #include<bits/stdc++.h> #define REP(i,m) for(int i=0;i<(m);++i) #define REPN(i,m,in) for(int i=(in);i<(m);++i) #define ALL(t) (t).begin(),(t).end() #define CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; #ifdef DEB #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl #define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} #else #define dump(x) ; #define dumpR(x) ; #define dumpY(x) ; #define dumpG(x) ; #define prl ; template<class T> void debug(T a,T b){ ;} #endif template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<lint,lint> pi; namespace std{ template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.fr<<','<<a.sc<<')'; return out; } } const lint INF=1e18; lint year,week; int n,m; lint D; lint ar[55]; pi br[100005]; vector<pi> eve[100005]; set<lint> S; lint cnt; bool ins(lint x){ if(S.count(x)) return false; auto it=S.lower_bound(x); lint r=*it; --it; lint l=*it; if(r-l-1>D){ if(r-x-1<=D) cnt+=r-x-1; if(x-l-1<=D) cnt+=x-l-1; ++cnt; } S.insert(x); return true; } void ers(lint x){ assert(S.count(x)==1); auto it=S.upper_bound(x); lint r=*it; --it;--it; lint l=*it; if(r-l-1<=D) ; else { if(r-x-1<=D) cnt-=r-x-1; if(x-l-1<=D) cnt-=x-l-1; --cnt; } S.erase(x); } void addAll(lint day){ vector<lint> did; REP(i,n){ if(ins(ar[i]+day)){ did.pb(ar[i]+day); } } printf("%lld\n",cnt); for(auto e:did) ers(e); } int main(){ cin>>year>>week>>n>>m>>D; S.insert(INF); S.insert(-INF); REP(i,n){ cin>>ar[i];--ar[i]; } REP(i,m){ cin>>br[i].fr>>br[i].sc; --br[i].fr;--br[i].sc; lint y=br[i].fr,w=br[i].sc; lint day=y*(lint)week+w; eve[w].pb({day,day+week}); ins(day); } REP(i,week){ addAll(i); sort(ALL(eve[i]),greater<pi>()); for(auto e:eve[i]){ ers(e.fr); ins(e.sc); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 祝日 |
User | hogloid |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2507 Byte |
Status | AC |
Exec Time | 2236 ms |
Memory | 14252 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 | 260 ms | 12928 KB |
01-02.txt | AC | 252 ms | 12288 KB |
01-03.txt | AC | 167 ms | 10880 KB |
01-04.txt | AC | 51 ms | 5504 KB |
01-05.txt | AC | 233 ms | 11392 KB |
01-06.txt | AC | 223 ms | 10880 KB |
01-07.txt | AC | 178 ms | 10344 KB |
01-08.txt | AC | 34 ms | 4864 KB |
01-09.txt | AC | 263 ms | 11904 KB |
01-10.txt | AC | 40 ms | 4864 KB |
01-11.txt | AC | 204 ms | 12544 KB |
01-12.txt | AC | 206 ms | 12032 KB |
01-13.txt | AC | 218 ms | 12032 KB |
01-14.txt | AC | 84 ms | 7040 KB |
01-15.txt | AC | 237 ms | 11776 KB |
01-16.txt | AC | 5 ms | 2688 KB |
01-17.txt | AC | 48 ms | 4992 KB |
01-18.txt | AC | 226 ms | 10880 KB |
01-19.txt | AC | 253 ms | 12928 KB |
01-20.txt | AC | 253 ms | 12416 KB |
02-01.txt | AC | 1810 ms | 14252 KB |
02-02.txt | AC | 747 ms | 11776 KB |
02-03.txt | AC | 830 ms | 12160 KB |
02-04.txt | AC | 1125 ms | 12160 KB |
02-05.txt | AC | 2146 ms | 12928 KB |
02-06.txt | AC | 1115 ms | 11776 KB |
02-07.txt | AC | 178 ms | 10344 KB |
02-08.txt | AC | 83 ms | 3712 KB |
02-09.txt | AC | 1425 ms | 12160 KB |
02-10.txt | AC | 117 ms | 4480 KB |
02-11.txt | AC | 1798 ms | 12672 KB |
02-12.txt | AC | 494 ms | 12032 KB |
02-13.txt | AC | 689 ms | 11648 KB |
02-14.txt | AC | 118 ms | 3968 KB |
02-15.txt | AC | 616 ms | 11648 KB |
02-16.txt | AC | 29 ms | 2688 KB |
02-17.txt | AC | 55 ms | 4992 KB |
02-18.txt | AC | 271 ms | 11008 KB |
02-19.txt | AC | 2236 ms | 12928 KB |
02-20.txt | AC | 172 ms | 10352 KB |
02-21.txt | AC | 426 ms | 3328 KB |
02-22.txt | AC | 3 ms | 2560 KB |
02-23.txt | AC | 1211 ms | 12672 KB |
02-24.txt | AC | 734 ms | 12288 KB |
02-25.txt | AC | 961 ms | 13568 KB |
02-26.txt | AC | 4 ms | 2560 KB |
02-27.txt | AC | 104 ms | 2688 KB |
02-28.txt | AC | 363 ms | 2944 KB |
02-29.txt | AC | 199 ms | 10496 KB |
02-30.txt | AC | 202 ms | 10624 KB |
02-31.txt | AC | 204 ms | 10624 KB |
02-32.txt | AC | 254 ms | 2816 KB |
sample-01.txt | AC | 2 ms | 2560 KB |
sample-02.txt | AC | 2 ms | 2560 KB |
sample-03.txt | AC | 2 ms | 2560 KB |
sample-04.txt | AC | 2 ms | 2560 KB |