Submission #171374

#TimeUsernameProblemLanguageResultExecution timeMemory
171374arnold518Dancing Elephants (IOI11_elephants)C++14
97 / 100
9041 ms11612 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include "elephants.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 150000; const int SQ = 390; int SQ2 = 400; int N, L, A[MAXN+10], B[MAXN+10], S[MAXN+10]; pii C[MAXN+10]; int P[MAXN/SQ+10][SQ*10+10], Q[MAXN/SQ+10][SQ*10+10], R[MAXN/SQ+10][SQ*10+10], sz[MAXN/SQ+10]; void calc(int num) { int i, j; sort(P[num], P[num]+sz[num]); for(i=0; i<=sz[num]; i++) Q[num][i]=R[num][i]=0; for(i=sz[num]-1; i>=0; i--) { int pos=upper_bound(P[num], P[num]+sz[num], P[num][i]+L)-P[num]; if(pos==sz[num]) Q[num][i]=P[num][i]+L, R[num][i]=1; else Q[num][i]=Q[num][pos], R[num][i]=R[num][pos]+1; } S[num]=P[num][0]; } void make() { int i, j; for(i=0; i<N; i++) C[i]={A[i], i}; sort(C, C+N); for(i=0; i<=(N-1)/SQ; i++) sz[i]=0; for(i=0; i<N; i++) P[i/SQ][sz[i/SQ]++]=C[i].first, B[C[i].second]=i/SQ; for(i=0; i<=(N-1)/SQ; i++) calc(i); } void pop(int p) { int i, j; int num=B[p]; for(i=0; i<sz[num]; i++) if(P[num][i]==A[p]) break; int pos=i; for(i=pos+1; i<sz[num]; i++) P[num][i-1]=P[num][i]; sz[num]--; calc(num); B[p]=-1; } void push(int p, int x) { int i, j; int num=upper_bound(S, S+(N-1)/SQ+1, x)-S-1; if(num==-1) num=0; P[num][sz[num]++]=x; calc(num); B[p]=num; } void init(int _N, int _L, int *X) { int i, j; N=_N; L=_L; SQ2=sqrt(N)+1; for(i=0; i<N; i++) A[i]=X[i]; make(); } int query() { int i, j; int bef=-1; int ans=0; for(i=0; i<=(N-1)/SQ; i++) { int pos=upper_bound(P[i], P[i]+sz[i], bef)-P[i]; if(pos==sz[i]) continue; ans+=R[i][pos]; bef=Q[i][pos]; } return ans; } int qcnt=0; int update(int p, int y) { int i, j; pop(p); push(p, y); A[p]=y; qcnt++; if(qcnt==SQ2) qcnt=0, make(); return query(); }

Compilation message (stderr)

elephants.cpp: In function 'void calc(int)':
elephants.cpp:23:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:37:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:47:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:61:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:61:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int query()':
elephants.cpp:82:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:99:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:99:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
#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...