Submission #1014756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014756		saayan007	Watering can (POI13_kon)	C++17	100 / 100	258 ms	27220 KiB

kon

#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 / 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