Submission #298981

#	Time	Username	Problem	Language	Result	Execution time	Memory
298981		MladenP	Watering can (POI13_kon)	C++17	100 / 100	3432 ms	22264 KiB

kon

#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 100000000
#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];
        lazy[node] = 0;
        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] = {0, 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++) {
        PRINT(D[i]);
        int idx = i+1;
        if(D[i] >= K) updBIT(idx, +1), update(1, 1, N, idx, idx, -INF);
        else update(1, 1, N, idx, idx, D[i]);
    }
    //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);
    while(rez.fi >= K) {
        update(1, 1, N, rez.se, rez.se, -INF);
        updBIT(rez.se, +1);
        rez = query(1, 1, N, 1, N);
    }
}

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10