oj.uz

Submission #298966

# Submission time Handle Problem Language Result Execution time Memory
298966 2020-09-14T11:19:49 Z MladenP Watering can (POI13_kon) C++17
0 / 100
 649 ms 17480 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define pll pair<lld,lld>
#define all(x) begin(x),end(x)
#define mid ((l+r)/2)
#define sz(x) int((x).size())
#define endl '\n'
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define INF 1000000000
#define pb push_back
using namespace std;
#define MAXN 300010

int N, K, bit[MAXN], lazy[4*MAXN];
pii seg[4*MAXN];
void updBIT(int idx, int val) {
    while(idx < MAXN) {
        bit[idx] += val;
        idx += idx&-idx;
    }
}
int queryBIT(int idx) {
    int rez = 0;
    while(idx) {
        rez += bit[idx];
        idx -= idx&-idx;
    }
    return rez;
}
void propagate(int node, int l, int r) {
    if(l == r) {
        seg[node].fi += lazy[node];
        return;
    }
    seg[node].fi += lazy[node];
    lazy[2*node] += lazy[node];
    lazy[2*node+1] += lazy[node];
    lazy[node] = 0;
}
pii query(int node, int l, int r, int L, int R) {
    propagate(node, l, r);
    if(r < l || R < L || r < L || R < l) return {-INF, -INF};
    if(L <= l && r <= R) return seg[node];
    return max(query(2*node, l, mid, L, R), query(2*node+1, mid+1, r, L, R));
}
void update(int node, int l, int r, int L, int R, int val) {
    propagate(node, l, r);
    if(r < l || R < L || r < L || R < l) return;
    if(L <= l && r <= R) {
        lazy[node] += val;
        propagate(node, l, r);
        return;
    }
    update(2*node, l, mid, L, R, val);
    update(2*node+1, mid+1, r, L, R, val);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void init(int node, int l, int r) {
    if(l == r) {
        seg[node] = {-INF, l};
        return;
    }
    init(2*node, l, mid); init(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void inicjuj(int n, int k, int *D)
{
    //PRINT(n);
    N = n, K = k;
    init(1, 1, N);
    //PRINT(22222);
    for(int i = 0; i < N; i++) {
        int idx = i+1;
        if(D[idx] >= K) updBIT(idx, +1), update(1, 1, N, idx, idx, -INF);
        else update(1, 1, N, idx, idx, D[idx]);
    }
    //PRINT(333333);
}

void podlej(int a, int b)
{
    a++; b++;
    update(1, 1, N, a, b, +1);
    pii rez = query(1, 1, N, 1, N);
    if(rez.fi >= K) {
        update(1, 1, N, rez.se, rez.se, -INF);
        updBIT(rez.se, +1);
    }
}

int dojrzale(int a, int b)
{
    a++; b++;
    return queryBIT(b)-queryBIT(a-1);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 5624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 6392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 6464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 10376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 649 ms 17272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 644 ms 17480 KB Output isn't correct
2 Halted 0 ms 0 KB -