Submission #197590

#TimeUsernameProblemLanguageResultExecution timeMemory
197590stefdascaWatering can (POI13_kon)C++14
30 / 100
4098 ms76952 KiB
#include<bits/stdc++.h> #include "koninc.h" using namespace std; const int MAXN = 300001, rad = 1502; 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) { 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 = 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); } void podlej(int a, int b) { int fini = R[buk[a]]; proc(buk[a]); while(a <= b && a <= fini) { ++v[a]; ++a; } proc(buk[a]); 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]]; proc(buk[a]); while(a <= b && a <= fini) { ++v[a]; ++a; } proc(buk[a]); } } int dojrzale(int a, int b) { int fini = R[buk[a]]; int qans = 0; proc(buk[a]); 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]); 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...