oj.uz

답안 #1014756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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