Submission #416011

#TimeUsernameProblemLanguageResultExecution timeMemory
416011CSQ31Dancing Elephants (IOI11_elephants)C++14
0 / 100
1 ms332 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound typedef long long int ll; typedef vector<vector<int>> vii; typedef pair<int,int> pii; int n,l; int x[1500001]; int blk = 500; struct bucket{ int sz; int x[1001]; int cnt[1001]; int reach[1001]; void calc(){ int t = sz; for(int i=sz-1;i>=0;i--){ while(t && x[t-1] > x[i]+l)t--; if(t == sz){ cnt[i] = 1; reach[i] = x[i]+l; }else{ cnt[i] = cnt[t]+1; reach[i] = reach[t]; } } } void add(int y){ int p = ub(x,x+sz,y) - x; sz++; for(int i=sz-1;i>p;i--)x[i] = x[i-1]; x[p] = y; calc(); } void del(int y){ int p = lb(x,x+sz,y) - x; sz--; for(int i=p;i<sz;i++)x[i] = x[i+1]; calc(); } }b[500]; int bcnt = 0; void init(int N, int L, int X[]) { n = N; l = L; for(int i=0;i<n;i++)x[i] = X[i]; for(int i=0;i<n;i+=blk){ for(int j=i;j<min(i+blk,n);j++){ b[bcnt].x[b[bcnt].sz++] = x[j]; } b[bcnt++].calc(); } //for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n'; //cout<<"BUILT"<<'\n'; } void rebuild(){ vector<int>nx; for(int i=0;i<bcnt;i++){ for(int j=0;j<b[i].sz;j++){ nx.pb(b[i].x[j]); } } bcnt = 0; for(int i=0;i<n;i+=blk){ b[bcnt].sz = 0; for(int j=i;j<min(i+blk,n);j++){ b[bcnt].x[b[bcnt].sz++] = nx[j]; } b[bcnt++].calc(); } } int num = 0; int update(int i, int y) { if(num == 400){rebuild();num=0;} int pv = x[i]; //cout<<"del"<<'\n'; for(int i=0;i<bcnt;i++){ if(b[i].x[0] <= pv && b[i].x[b[i].sz-1] >= pv){ b[i].del(y); break; } } //for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n'; x[i] = y; for(int i=0;i<bcnt;i++){ if((i == 0 || b[i].x[0] <= y) && (i == bcnt-1 || (b[i+1].x[0] > y))){ b[i].add(y); break; } } //cout<<"add"<<'\n'; //for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n'; int ans = 0; int cur = -1; for(int i=0;i<bcnt;i++){ if(cur>=b[i].x[b[i].sz-1])continue; if(cur < b[i].x[0]){ ans+=b[i].cnt[0]; cur = b[i].reach[0]; continue; } int p = ub(b[i].x,b[i].x+b[i].sz,cur) - b[i].x; ans+=b[i].cnt[p]; cur=b[i].reach[p]; } num++; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...