Submission #799225

#TimeUsernameProblemLanguageResultExecution timeMemory
799225baneWatering can (POI13_kon)C++17
70 / 100
2932 ms131072 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <queue> #include <set> #include <unordered_map> #include <unordered_set> #include <string> #include <string.h> #include <bitset> #include <numeric> #include <utility> #include<math.h> using namespace std; #define ll long long const int nax = 300'001; int sq = 1000; ll N, K, t[nax], zers[nax], ans[nax]; int mapa[301][300001]; void inicjuj(int n, int k, int *D) { //sq = min(550, (int)sqrt(n) + 1); for (int i = 0; i < n; i++){ t[i] = D[i]; } N = n, K = k; for (int i = 0; i < n; i++){ if (K >= t[i] && K - t[i] <= 300000) mapa[i / sq][-(K - t[i]) + 300000]++; if (t[i] >= K)ans[i / sq]++; } } void podlej(int a, int b) { //--a,--b; int from = a/sq, to = (b / sq); for (int i = from; i <= to; i++){ if (a <= i * sq && b >= (i + 1) * sq - 1){ zers[i]++; if (zers[i] <= 300000)ans[i] += mapa[i][300000 - zers[i]]; }else{ ans[i] = 0; for (int j = i * sq; j / sq == i && j < N; j++){ if (K >= t[j] && K - t[j] <= 300000) mapa[i][-(K - t[j]) + 300000]--; t[j] += zers[i]; if (j >= a && j <= b)t[j]++; if (K >= t[j] && K - t[j] <= 300000){ mapa[i][- (K - t[j]) + 300000]++; } if (t[j] >= K)ans[i]++; } zers[i] = 0; } } } int dojrzale(int a, int b) { // --a,--b; int odg = 0; int from = a/sq, to = (b / sq); for (int i = from; i <= to; i++){ if (a <= i * sq && b >= (i + 1) * sq - 1){ odg += ans[i]; }else{ for (int j = max(a, i * sq); j / sq == i && j <= b; j++){ odg += (t[j] + zers[i] >= K); } } } return odg; }
#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...