Submission #799218

# Submission time Handle Problem Language Result Execution time Memory
799218 2023-07-31T10:50:32 Z Blagoj Watering can (POI13_kon) C++17
60 / 100
1623 ms 131072 KB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nax = 300'001;
int sq = 500;
ll N, K, t[nax], zers[nax], ans[nax];
 
int mapa[601][300005];
 
void inicjuj(int n, int k, int *D)
{
    sq = min(500, (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] <= 299999)
            mapa[i / sq][299999 - (K - t[i])]++;
        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]++;
            ans[i] += mapa[i][299999 - zers[i]];
        }else{
            ans[i] = 0;
            for (int j = i * sq; j / sq == i && j < N; j++){
                if (K >= t[j] && K - t[j] <= 299999)
                    mapa[i][-(K - t[j]) + 299999]--;
                t[j] += zers[i];
                if (j >= a && j <= b)t[j]++;
                if (K >= t[j] && K - t[j] <= 299999){
                    mapa[i][-(K - t[j])+ 299999]++;
                }
                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 time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 3 ms 2132 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 83 ms 2520 KB Output is correct
2 Correct 77 ms 2284 KB Output is correct
3 Correct 68 ms 2848 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 129 ms 2944 KB Output is correct
2 Correct 183 ms 4192 KB Output is correct
3 Correct 139 ms 3248 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 367 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1378 ms 19568 KB Output is correct
2 Correct 1100 ms 12944 KB Output is correct
3 Correct 1366 ms 17648 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1444 ms 18244 KB Output is correct
2 Correct 1262 ms 16884 KB Output is correct
3 Correct 1623 ms 8520 KB Output is correct