Submission #197597

#TimeUsernameProblemLanguageResultExecution timeMemory
197597stefdascaWatering can (POI13_kon)C++14
20 / 100
4096 ms10412 KiB
#include<bits/stdc++.h> #include "koninc.h" using namespace std; const int MAXN = 300001, rad = 6000; int N, K, v[MAXN+5], done = 200000; int buk[MAXN+5], L[1012], R[1012], ad[1012], nrbuk, aans[1012]; short ans[502][100012]; void proc(int bk, int LL, int RR) { for(int j = L[bk]; j <= R[bk]; ++j) { if(v[j] >= K) ans[bk][0] = 0; else if(K - v[j] <= 100000) ans[bk][K - v[j]] = 0; } for(int j = LL; j <= RR; ++j) v[j]++; for(int j = L[bk]; j <= R[bk]; ++j) { v[j] += ad[bk]; if(v[j] >= K) ans[bk][0]++; else if(K - v[j] <= 100000) ans[bk][K - v[j]]++; } ad[bk] = 0; aans[bk] = ans[bk][0]; } void inicjuj(int n, int k, int *D) { N = n, K = k; for(int i = 0; i < n; ++i) v[i] = D[i]; for(int i = 0; i < n; ++i) { if(i % rad == 0) ++nrbuk, L[nrbuk] = i; R[nrbuk] = i; buk[i] = nrbuk; } for(int i = 0; i <= nrbuk; ++i) proc(i, 1, 0); } void podlej(int a, int b) { int fini = R[buk[a]]; int ax = buk[a]; proc(ax, a, min(b, fini)); a = min(b, fini) + 1; while(a < N && R[buk[a]] <= b) ++ad[buk[a]], aans[buk[a]] = aans[buk[a]] + ans[buk[a]][ad[buk[a]]], a = R[buk[a]] + 1; if(a <= b) { fini = R[buk[a]]; ax = buk[a]; proc(ax, a, b); } --done; } int dojrzale(int a, int b) { int fini = R[buk[a]]; int qans = 0; proc(buk[a], 1, 0); while(a <= b && a <= fini) { if(v[a] >= K) ++qans; ++a; } while(a < N && R[buk[a]] <= b) qans += aans[buk[a]], a = R[buk[a]] + 1; if(a <= b) { proc(buk[a], 1, 0); fini = R[buk[a]]; while(a <= b && a <= fini) { if(v[a] >= K) ++qans; ++a; } } --done; return qans; }
#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...
#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...