Submission #731049

#TimeUsernameProblemLanguageResultExecution timeMemory
731049ogibogi2004Holiday (IOI14_holiday)C++14
Compilation error
0 ms0 KiB
#include "elephants.h" #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+6; const int K=333; int dp1[MAXN]; int dp2[MAXN]; int where[MAXN]; int where1[MAXN]; set<pair<int,int> >alle; int cam; struct bucket { set<pair<int,int> >s; void compute() { auto it=s.end(); for(;;) { if(it==s.begin()) { break; } it--; int t=(*it).first+cam+1; auto it1=s.lower_bound({t,-1}); if(it1==s.end()) { dp1[(*it).second]=1; dp2[(*it).second]=t-1; } else { dp1[(*it).second]=dp1[(*it1).second]+1; dp2[(*it).second]=dp2[(*it1).second]; } } } }b[K]; int n; int get_ans() { int T=n/K+2; int lastb=(n-1)/T; int firstnz=-1; for(int i=0;i<=lastb;i++) { if(b[i].s.size()==0)continue; firstnz=i; break; } int t=(*b[firstnz].s.begin()).second; int last=dp2[t]; int ret=dp1[t]; //cout<<"starting from "<<t<<endl; for(int i=firstnz+1;i<=lastb;i++) { if(b[i].s.size()==0)continue; auto it=b[i].s.lower_bound({last+1,0}); if(it==b[i].s.end())continue; last=dp2[(*it).second]; ret+=dp1[(*it).second]; } return ret; } void construct_whole() { vector<pair<int,int> >ve; for(int i=1;i<=n;i++) { ve.push_back({where[i],i}); } sort(ve.begin(),ve.end()); int T=n/K+2; for(int i=0;i<ve.size();i++) { alle.insert(ve[i]); where[ve[i].second]=ve[i].first; where1[ve[i].second]=i/T; b[i/T].s.insert(ve[i]); } for(int i=0;i<=(ve.size()-1)/T;i++) { b[i].compute(); } } void init(int N, int L, int X[]) { n = N; cam = L; for(int i=0;i<N;i++) { where[i+1]=X[i]; } construct_whole(); } int cnt=0; int update(int i, int y) { i++; int j=where1[i]; b[j].s.erase({where[i],i}); int T=n/K+2; int lastb=(n-1)/T; int new_j=lastb; if((*b[1].s.begin()).first>y) { new_j=0; } else { for(int j=1;j<lastb;j++) { if((*b[j+1].s.begin()).first>y) { new_j=j; break; } } } b[new_j].s.insert({y,i}); b[new_j].compute(); where[i]=y; where1[i]=new_j; if(j!=new_j)b[j].compute(); cnt++; if(cnt%max(1,T-3)==0) { construct_whole(); } return get_ans(); }

Compilation message (stderr)

holiday.cpp:1:10: fatal error: elephants.h: No such file or directory
    1 | #include "elephants.h"
      |          ^~~~~~~~~~~~~
compilation terminated.