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
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 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