Submission #233917

#TimeUsernameProblemLanguageResultExecution timeMemory
233917crossing0verDancing Elephants (IOI11_elephants)C++17
0 / 100
5 ms384 KiB
#include <bits/stdc++.h> #include "elephants.h" using namespace std; const int K = 400, MXN = 1.5E5 + 5; const int B = MXN/K + 5; int P[150000], inbox[150000] , L, n; struct BLOCK{ int sz; int arr[K*2 + 10] , last[K*2 + 10], cost[K*2 + 10]; void del(int x) { for (int i = 0; i < sz; i++) if (arr[i] == x) { x = i; break; } for (; x < sz;x++) swap(arr[x],arr[x+1]); sz--; } void insert (int x) { arr[sz] = x; int pos = sz; for ( ; pos > 0 && P[x] < P[ arr[pos - 1] ]; pos--) swap(arr[pos],arr[pos - 1]); sz++; } void slv() { int ptr = sz - 1; for (int i = sz - 1; i >= 0; i--) { while (ptr > 0 && P[arr[i]] + L < P[arr[ptr - 1]]) ptr--; if (P[arr[i]] + L>= P[arr[sz - 1]]) cost[i] = 1, last[i] = arr[i]; else cost[i] = 1 + cost[ptr], last[i] = last[ptr]; } } int get (int val) { if (sz == 0 ) return -1; int l = 0, r = sz - 1; while ( l != r) { int m = (l + r)/2; if (P[arr[m]] > val) r = m; else l = m + 1; } if (P[arr[r]] <= val) return -1; return r; } } box[MXN/K + 10]; void build() { int blc = -1; for (int i = 0; i < n; i++) { if (i % K == 0){ blc++; } box[blc].insert(i); inbox[i] = blc; } for (int i= 0; i <= B; i++) box[i].slv(); } void init(int N, int L1, int X[]) { n = N; L = L1; for (int i = 0; i < n; i++) P[i] = X[i]; build(); } int update(int i, int y) { box[inbox[i]].del(i); box[inbox[i]].slv(); P[i] = y; for (int j = 0; j <= B; j++) { if ((!box[j].sz || P[box[j].arr[box[j].sz - 1]] > y) || j == B) { box[j].insert(i),inbox[i] = j, box[j].slv(); break; } } int val = INT_MIN,ans = 0; for (int i = 0; i <= B; i++) { int pos = box[i].get(val + L); if (pos == -1) continue; ans++; val = P[box[i].last[pos]]; } return ans; } /* main(){ int N,L1,q; cin >> N >> L1 >> q; int X[N]; for (int i = 0 ; i< N ; i ++) cin >> X[i]; init(N,L1,X); while (q--) { int i,y; cin >> i >> y; cout << update(i,y) <<'\n'; } } */ /* 4 10 5 10 15 17 20 */
#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...