Submission #197592

#TimeUsernameProblemLanguageResultExecution timeMemory
197592stefdascaWatering can (POI13_kon)C++14
50 / 100
4099 ms83452 KiB
#include<bits/stdc++.h> #include "koninc.h" using namespace std; const int MAXN = 300001, rad = 1500; int N, K, v[MAXN+5]; int buk[MAXN+5], L[1012], R[1012], ad[1012], nrbuk, aans[1012]; short ans[202][300012]; 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] <= 300000) 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] <= 300000) 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); } } 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; } } 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...