Submission #299037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
299037	2020-09-14T12:36:11 Z	jovan_b	Watering can (POI13_kon)	C++17	100 / 100	473 ms	19576 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);
    //cout << "ovde " << l << " " << r << " " << tl << " " << tr << " " << val << endl;
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        //cout << "ovde " << l << " " << r << " " << tl << " " << tr << " " << val << endl;
        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);
    }
    //cout << "gotovo" << " " << getbit(N) << endl;
}

void podlej(int a, int b)
{
    a++;
    b++;
    upd(1, 1, N, a, b, 1);
    //cout << "gotov" << endl;
    while(seg[1].mx >= K){
        //cout << seg[1].mx << " " << seg[1].idx << endl;
        addbit(seg[1].idx);
        upd(1, 1, N, seg[1].idx, seg[1].idx, -INF);
    }
}

int dojrzale(int a, int b)
{
    a++;
    b++;
    //cout << getbit(b) << " " << getbit(a-1) << endl;
    return getbit(b) - getbit(a-1);
}

/*
4 6
5 4 3 7
6

*/

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	2 ms	384 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	2552 KB	Output is correct
2	Correct	60 ms	2732 KB	Output is correct
3	Correct	45 ms	2936 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	2680 KB	Output is correct
2	Correct	100 ms	4600 KB	Output is correct
3	Correct	84 ms	4600 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	5880 KB	Output is correct
2	Correct	113 ms	6776 KB	Output is correct
3	Correct	113 ms	5124 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	222 ms	6136 KB	Output is correct
2	Correct	153 ms	7288 KB	Output is correct
3	Correct	223 ms	7032 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	288 ms	6264 KB	Output is correct
2	Correct	244 ms	10744 KB	Output is correct
3	Correct	224 ms	7420 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	388 ms	10360 KB	Output is correct
2	Correct	464 ms	11128 KB	Output is correct
3	Correct	424 ms	11512 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	473 ms	17528 KB	Output is correct
2	Correct	349 ms	19348 KB	Output is correct
3	Correct	421 ms	18504 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	469 ms	17604 KB	Output is correct
2	Correct	416 ms	19576 KB	Output is correct
3	Correct	473 ms	18256 KB	Output is correct

Submission #299037

Compilation message