Submission #1014756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014756	2024-07-05T13:05:17 Z	saayan007	Watering can (POI13_kon)	C++17	100 / 100	258 ms	27220 KB

#include "bits/stdc++.h"
using namespace std;
const int mxn = 3e5 + 10;
const int inf = 1e6;
int diff[mxn];
int n, k, m;
vector<int> st, rp, lz;
const char nl = '\n';

void app(int x, int v) {
    st[x] += v;
    lz[x] += v;
}

void push(int x) {
    if(x < m && lz[x] != 0) {
        app(2*x, lz[x]);
        app(2*x + 1, lz[x]);
    }
    lz[x] = 0;
}

void kill(int x = 1, int lx = 0, int rx = m - 1) {
    if(st[x] < 0) return;
    push(x);
    if(lx == rx) {
        st[x] = -inf;
        rp[x] = 1;
        return;
    }
    int d = (lx + rx) / 2;
    kill(2*x, lx, d);
    kill(2*x + 1, d + 1, rx);
    st[x] = max(st[2*x], st[2*x + 1]);
    rp[x] = rp[2*x] + rp[2*x + 1];
}

void mod(int l, int r, int v = 1, int x = 1, int lx = 0, int rx = m - 1) {
    push(x);
    if(r < lx || rx < l) return;
    if(l <= lx && rx <= r) {
        app(x, v);
        return;
    }
    int d = (lx + rx) / 2;
    mod(l, r, v, 2*x, lx, d);
    mod(l, r, v, 2*x + 1, d + 1, rx);
    st[x] = max(st[2*x], st[2*x + 1]);
    rp[x] = rp[2*x] + rp[2*x + 1];
}

int qry(int l, int r, int x = 1, int lx = 0, int rx = m - 1) {
    push(x);
    if(r < lx || rx < l) return 0;
    if(l <= lx && rx <= r) {
        return rp[x];
    }
    int d = (lx + rx) / 2;
    return qry(l, r, 2*x, lx, d) + qry(l, r, 2*x + 1, d + 1, rx);
}

void print() {
    /* for(int i = 1; i < 2*n; ++i) { */
    /*     cout << "("; */
    /*     if(st[i] < -1000) cout << "- "; */
    /*     else cout << st[i] << ' '; */
    /*     if(lz[i] < -1000) cout << "- "; */
    /*     else cout << lz[i] << ' '; */
    /*     if(rp[i] < -1000) cout << "-"; */
    /*     else cout << rp[i]; */
    /*     cout << ") "; */
    /*     if(i & (i + 1)); */
    /*     else cout << "\n"; */
    /* } */
    /* cout << '\n'; */
}

void inicjuj(int N, int K, int *D) // initialise
{
    k = K;
    n = N;

    m = 1; while(m < N) m *= 2;
    st.resize(2*m, -1); rp.resize(2*m); lz.resize(2*m);
    for(int i = 0; i < N; ++i) {
        st[i + m] = D[i] - k;
    }
    for(int i = m - 1; i > 0; --i) {
        st[i] = max(st[2*i], st[2*i + 1]);
    }
    /* print(); */
}

void podlej(int a, int b) // add 1 to [a, b]
{
    /* cout << "mod: " << a << ' ' << b << nl; */
    mod(a, b);

    /* print(); */
}

int dojrzale(int a, int b) // report num ripe in [a, b]
{
    kill();
    /* cout << "kill\n"; */
    /* print(); */
    int ret = qry(a, b);
    /* cout << "qry: " << a << ' ' << b << nl; */
    /* print(); */
    return ret;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	3944 KB	Output is correct
2	Correct	33 ms	3928 KB	Output is correct
3	Correct	29 ms	4176 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	5324 KB	Output is correct
2	Correct	49 ms	5460 KB	Output is correct
3	Correct	43 ms	5456 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	7908 KB	Output is correct
2	Correct	80 ms	8016 KB	Output is correct
3	Correct	74 ms	6992 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	11600 KB	Output is correct
2	Correct	91 ms	10064 KB	Output is correct
3	Correct	107 ms	10580 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	12104 KB	Output is correct
2	Correct	113 ms	13396 KB	Output is correct
3	Correct	136 ms	12368 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	17732 KB	Output is correct
2	Correct	229 ms	16076 KB	Output is correct
3	Correct	195 ms	18980 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	255 ms	26448 KB	Output is correct
2	Correct	253 ms	25756 KB	Output is correct
3	Correct	258 ms	26960 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	255 ms	26708 KB	Output is correct
2	Correct	246 ms	27220 KB	Output is correct
3	Correct	220 ms	26452 KB	Output is correct

Submission #1014756

Compilation message