Submission #298981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
298981	2020-09-14T11:33:48 Z	MladenP	Watering can (POI13_kon)	C++17	100 / 100	3432 ms	22264 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 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.0 / 10.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	504 KB	Output is correct
2	Correct	16 ms	512 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	348 ms	2016 KB	Output is correct
2	Correct	282 ms	2944 KB	Output is correct
3	Correct	263 ms	2872 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	429 ms	3072 KB	Output is correct
2	Correct	534 ms	4216 KB	Output is correct
3	Correct	499 ms	3960 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	936 ms	5496 KB	Output is correct
2	Correct	814 ms	6540 KB	Output is correct
3	Correct	654 ms	4600 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1381 ms	6776 KB	Output is correct
2	Correct	838 ms	7032 KB	Output is correct
3	Correct	1157 ms	6444 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1457 ms	7116 KB	Output is correct
2	Correct	1643 ms	11252 KB	Output is correct
3	Correct	1367 ms	7416 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2453 ms	12184 KB	Output is correct
2	Correct	2509 ms	12812 KB	Output is correct
3	Correct	2514 ms	12024 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3322 ms	20972 KB	Output is correct
2	Correct	3191 ms	22116 KB	Output is correct
3	Correct	2969 ms	18832 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3263 ms	20952 KB	Output is correct
2	Correct	3273 ms	22264 KB	Output is correct
3	Correct	3432 ms	18512 KB	Output is correct

Submission #298981

Compilation message