oj.uz

Submission #453791

# Submission time Handle Problem Language Result Execution time Memory
453791 2021-08-04T21:31:28 Z JovanB Watering can (POI13_kon) C++17
100 / 100
 469 ms 29552 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int N, K, t[10];
 
int n;
 
struct segment{
    int mx, idx, lazy;
} seg[2000005];
 
int bit[300005];
int niz[300005];
 
const int INF = 1000000000;
 
int getbit(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}
 
void addbit(int x){
    while(x <= 300000){
        bit[x]++;
        x += x & -x;
    }
}
 
void propagate(int node, int l, int r){
    seg[node].mx += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}
 
void init(int node, int l, int r){
    if(l == r){
        seg[node].mx = niz[l];
        seg[node].idx = l;
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
    seg[node].idx = seg[node*2+1].idx;
    if(seg[node].mx == seg[node*2].mx) seg[node].idx = seg[node*2].idx;
}
 
void upd(int node, int l, int r, int tl, int tr, int val){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy += val;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
 
    seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
    seg[node].idx = seg[node*2+1].idx;
    if(seg[node].mx == seg[node*2].mx) seg[node].idx = seg[node*2].idx;
}
 
void inicjuj(int n, int k, int *D)
{
    N = n, K = k;
    for(int i=1; i<=N; i++) niz[i] = D[i-1];
    init(1, 1, N);
    while(seg[1].mx >= K){
        addbit(seg[1].idx);
        upd(1, 1, N, seg[1].idx, seg[1].idx, -INF);
    }
}
 
void podlej(int a, int b)
{
    a++;
    b++;
    upd(1, 1, N, a, b, 1);
    while(seg[1].mx >= K){
        addbit(seg[1].idx);
        upd(1, 1, N, seg[1].idx, seg[1].idx, -INF);
    }
}
 
int dojrzale(int a, int b)
{
    a++;
    b++;
    return getbit(b) - getbit(a-1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1484 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 1612 KB Output is correct
2 Correct 6 ms 1612 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4188 KB Output is correct
2 Correct 56 ms 4036 KB Output is correct
3 Correct 49 ms 4096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5728 KB Output is correct
2 Correct 93 ms 5808 KB Output is correct
3 Correct 84 ms 5816 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8572 KB Output is correct
2 Correct 107 ms 8484 KB Output is correct
3 Correct 108 ms 7308 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 12536 KB Output is correct
2 Correct 126 ms 10528 KB Output is correct
3 Correct 227 ms 11396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12928 KB Output is correct
2 Correct 247 ms 14440 KB Output is correct
3 Correct 211 ms 13076 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 19340 KB Output is correct
2 Correct 461 ms 17704 KB Output is correct
3 Correct 428 ms 20640 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 28592 KB Output is correct
2 Correct 310 ms 28156 KB Output is correct
3 Correct 412 ms 28556 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 29212 KB Output is correct
2 Correct 370 ms 29552 KB Output is correct
3 Correct 469 ms 28544 KB Output is correct