oj.uz

Submission #482117

# Submission time Handle Problem Language Result Execution time Memory
482117 2021-10-23T08:58:47 Z MilosMilutinovic Watering can (POI13_kon) C++14
100 / 100
 301 ms 32620 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back

#define gas INT_MAX

using namespace std;

int N,K;

int niz[300005];

int mn[2500005];
int cnt[2500005];
int lzy[2500005];

int inf = 1e9+200;

void upd(int node){
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
}

void build(int node, int l, int r){
    if(l == r){
        if(niz[l] > 0)mn[node] = niz[l];
        else{
            cnt[node] = 1;
            mn[node] = inf;
        }
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    upd(node);
}

void propagate(int node){
    if(mn[node] != inf)mn[node] -= lzy[node];
    lzy[node * 2] += lzy[node];
    lzy[node * 2 + 1] += lzy[node];
    lzy[node] = 0;
}

void update(int node, int l, int r, int ll, int rr, int x){
    propagate(node);
    if(l > r || l > rr || r < ll)return;
    if(ll <= l && r <= rr){
        lzy[node] += x;
        propagate(node);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, ll, rr, x);
    update(node * 2 + 1, mid + 1, r, ll, rr, x);
    upd(node);
}

int get(int node, int l, int r, int ll, int rr){
    //propagate(node);
    if(l > r || l > rr || r < ll)return 0;
    if(ll <= l && r <= rr)return cnt[node];
    int mid = (l + r) / 2;
    return get(node * 2, l, mid, ll, rr) + get(node * 2 + 1, mid + 1, r, ll, rr);
}

void rebuild(int node, int l, int r){
    propagate(node);
    if(mn[node] > 0)return;
    if(l == r){
        mn[node] = inf;
        cnt[node] = 1;
        return;
    }
    int mid = (l + r) / 2;
    rebuild(node * 2, l, mid);
    rebuild(node * 2 + 1, mid + 1, r);
    upd(node);
}

void inicjuj(int n, int k, int *D)
{
    N = n;
    K = k;
    ff(i,1,n)niz[i] = k-D[i-1];
    build(1, 1, N);
}

void podlej(int a, int b)
{
    a++;
    b++;
    update(1, 1, N, a, b, 1);
    rebuild(1, 1, N);
}

int dojrzale(int a, int b)
{
    a++;
    b++;
    return get(1, 1, N, a, b);
}

Compilation message

kon.cpp: In function 'void inicjuj(int, int, int*)':
kon.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
kon.cpp:87:5: note: in expansion of macro 'ff'
   87 |     ff(i,1,n)niz[i] = k-D[i-1];
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1496 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2724 KB Output is correct
2 Correct 44 ms 2636 KB Output is correct
3 Correct 34 ms 2380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3932 KB Output is correct
2 Correct 60 ms 3692 KB Output is correct
3 Correct 65 ms 3812 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6184 KB Output is correct
2 Correct 65 ms 6276 KB Output is correct
3 Correct 76 ms 4064 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6812 KB Output is correct
2 Correct 111 ms 6776 KB Output is correct
3 Correct 138 ms 6084 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 6872 KB Output is correct
2 Correct 135 ms 10612 KB Output is correct
3 Correct 154 ms 5828 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 11568 KB Output is correct
2 Correct 254 ms 10668 KB Output is correct
3 Correct 259 ms 11376 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 20548 KB Output is correct
2 Correct 267 ms 31048 KB Output is correct
3 Correct 275 ms 28628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20420 KB Output is correct
2 Correct 299 ms 32620 KB Output is correct
3 Correct 288 ms 29476 KB Output is correct