oj.uz

Submission #754799

# Submission time Handle Problem Language Result Execution time Memory
754799 2023-06-08T14:39:39 Z Pring Fire (JOI20_ho_t5) C++14
100 / 100
 478 ms 71428 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

enum OP_TYPE {
    ADD,
    QUERY
};

struct Q {
    int t, l, r;
};

struct TRI {
    int x, y, val;
};

struct OP {
    OP_TYPE type;
    int t, id;
};

const int MXN = 200005;
int n, q, a[MXN], ans[MXN], lm[MXN], rm[MXN], opsz;
Q ask[MXN];
TRI tri[MXN * 4];
OP op[MXN * 5];

struct BIT {
    int val[MXN * 2], head, n;
    void init(int _n) {
        head = _n;
        n = 2 * _n;
    }
    void modify(int pos, int _val) {
        for (; pos <= n; pos += (pos & (-pos))) val[pos] += _val;
    }
    void modify_EX(int pos, int _val) {
        int pos0 = pos;
        for (; pos <= n; pos += (pos & (-pos))) val[pos] += _val * pos0;
    }
    int query(int pos) {
        int ans = 0;
        for (; pos > 0; pos -= (pos & (-pos))) ans += val[pos];
        return ans;
    }
    int rquery(int l, int r) {
        return query(r) - query(l - 1);
    }
} B[6];

struct DS1 {
    BIT *normal;
    void modify(int pos, int _val) {
        normal -> modify(normal -> head + pos, _val);
    }
    int query(int pos) {
        return normal -> query(normal -> head + pos);
    }
} ds1, ds2;

// struct DS2 {
//     BIT *normal;
//     void modify(int pos, int _val) {
//         normal -> modify(normal -> head + pos, _val);
//     }
//     int query(int pos) {
//         return normal -> query(normal -> head + pos);
//     }
// } ds2;

struct DS3 {
    BIT *normal, *special;
    void modify(int pos, int _val) {
        normal -> modify(normal -> head + pos, _val);
        special -> modify_EX(normal -> head + pos, _val);
    }
    int query(int pos) {
        return special -> rquery(special -> head + 1, special -> head + pos) - special -> head * normal -> rquery(normal -> head + 1, normal -> head + pos);
    }
} ds3, ds4;

// struct DS4 {
//     BIT *normal, *special;
//     void modify(int pos, int _val) {
//         normal -> modify(normal -> head + pos, _val);
//         special -> modify_EX(normal -> head + pos, _val);
//     }
//     int query(int pos) {
//         return special -> rquery(special -> head + 1, special -> head + pos) - special -> head * normal -> rquery(normal -> head + 1, normal -> head + pos);
//     }
// } ds4;

void MAKE_PLO() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) {
            rm[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        rm[st.top()] = n + 1;
        st.pop();
    }
    for (int i = n; i > 0; i--) {
        while (st.size() && a[st.top()] < a[i]) {
            lm[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        lm[st.top()] = 0;
        st.pop();
    }
    // for (int i = 1; i <= n; i++) cout << lm[i] << ' ';
    // cout << endl;
    // for (int i = 1; i <= n; i++) cout << rm[i] << ' ';
    // cout << endl;
    int h, w;
    for (int i = 1; i <= n; i++) {
        if (lm[i] == 0) h = n;
        else h = i - lm[i];
        w = rm[i] - i;
        tri[4 * i - 4] = {i, 0, a[i]};
        tri[4 * i - 3] = {i, h, -a[i]};
        tri[4 * i - 2] = {i + w, w, -a[i]};
        tri[4 * i - 1] = {i + w, h + w, a[i]};
    }
    // for (int i = 0; i < 4 * n; i++) cout << '<' << tri[i].x << ' ' << tri[i].y << ' ' << tri[i].val << '>' << endl;
}

void MAKE_OP() {
    for (int i = 0; i < 4 * n; i++) {
        op[i] = {ADD, tri[i].y, i};
    }
    for (int i = 4 * n; i < 4 * n + q; i++) {
        op[i] = {QUERY, ask[i - 4 * n].t, i - 4 * n};
    }
    sort(op, op + 4 * n + q, [](OP a, OP b) {
        if (a.t != b.t) return a.t < b.t;
        if (a.type != b.type) return a.type == ADD;
        return a.id < b.id;
    });
    opsz = 4 * n + q;
}

void INIT_SMG() {
    for (int i = 0; i < 6; i++) B[i].init(n);
    ds1.normal = &B[0];
    ds2.normal = &B[1];
    ds3.normal = &B[2];
    ds3.special = &B[3];
    ds4.normal = &B[4];
    ds4.special = &B[5];
}

void NEXT() {
    // cout << "NEXT" << endl;
    B[1].head--;
    B[4].head--;
    B[5].head--;
}

void ADD_TRI(int id) {
    TRI &tg = tri[id];
    // cout << "ADD_TRI ";
    // cout << '<' << tg.x << ' ' << tg.y << ' ' << tg.val << '>' << endl;
    ds1.modify(tg.x, tg.val);
    ds2.modify(tg.x + 1, -tg.val);
    ds3.modify(tg.x, tg.val);
    ds4.modify(tg.x + 1, -tg.val);
}

int PRECALC(int pos) {
    // cout << ds1.query(pos) << ' ' << ds2.query(pos) << ' ' << ds3.query(pos) << ' ' << ds4.query(pos) << endl;
    return (pos + 1) * (ds1.query(pos) + ds2.query(pos)) - (ds3.query(pos) + ds4.query(pos));
}

int GETANS(int id) {
    Q &tg = ask[id];
    // cout << "GETANS ";
    // cout << '<' << tg.t << ' ' << tg.l << ' ' << tg.r << '>' << endl;
    return PRECALC(tg.r) - PRECALC(tg.l - 1);
    // return 0;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < q; i++) {
        cin >> ask[i].t >> ask[i].l >> ask[i].r;
        if (ask[i].t >= n) ask[i].t = n - 1;
    }
    MAKE_PLO();
    MAKE_OP();
    INIT_SMG();
    for (int i = 0; i < opsz; i++) {
        if (op[i].t == n) break;
        // if (i && op[i].t > op[i - 1].t) NEXT();
        for (int j = op[i - 1].t; j < op[i].t; j++) NEXT();
        if (op[i].type == ADD) ADD_TRI(op[i].id);
        else ans[op[i].id] = GETANS(op[i].id);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 400 ms 64320 KB Output is correct
3 Correct 401 ms 69440 KB Output is correct
4 Correct 438 ms 69868 KB Output is correct
5 Correct 428 ms 70852 KB Output is correct
6 Correct 439 ms 69708 KB Output is correct
7 Correct 391 ms 70520 KB Output is correct
8 Correct 411 ms 70972 KB Output is correct
9 Correct 421 ms 70584 KB Output is correct
10 Correct 459 ms 69144 KB Output is correct
11 Correct 433 ms 70972 KB Output is correct
12 Correct 410 ms 68972 KB Output is correct
13 Correct 441 ms 70400 KB Output is correct
14 Correct 382 ms 70224 KB Output is correct
15 Correct 393 ms 70508 KB Output is correct
16 Correct 402 ms 69828 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 406 ms 63424 KB Output is correct
3 Correct 390 ms 67784 KB Output is correct
4 Correct 388 ms 70372 KB Output is correct
5 Correct 384 ms 68300 KB Output is correct
6 Correct 392 ms 69056 KB Output is correct
7 Correct 375 ms 69324 KB Output is correct
8 Correct 393 ms 68760 KB Output is correct
9 Correct 473 ms 68196 KB Output is correct
10 Correct 395 ms 67460 KB Output is correct
11 Correct 400 ms 70188 KB Output is correct
12 Correct 394 ms 69480 KB Output is correct
13 Correct 404 ms 69860 KB Output is correct
14 Correct 419 ms 68328 KB Output is correct
15 Correct 389 ms 69888 KB Output is correct
16 Correct 419 ms 69240 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 62628 KB Output is correct
2 Correct 342 ms 62968 KB Output is correct
3 Correct 362 ms 64504 KB Output is correct
4 Correct 347 ms 62632 KB Output is correct
5 Correct 347 ms 62756 KB Output is correct
6 Correct 363 ms 63128 KB Output is correct
7 Correct 348 ms 64176 KB Output is correct
8 Correct 361 ms 63636 KB Output is correct
9 Correct 360 ms 62772 KB Output is correct
10 Correct 343 ms 63612 KB Output is correct
11 Correct 374 ms 63160 KB Output is correct
12 Correct 357 ms 63296 KB Output is correct
13 Correct 369 ms 62984 KB Output is correct
14 Correct 385 ms 63200 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 400 ms 64320 KB Output is correct
34 Correct 401 ms 69440 KB Output is correct
35 Correct 438 ms 69868 KB Output is correct
36 Correct 428 ms 70852 KB Output is correct
37 Correct 439 ms 69708 KB Output is correct
38 Correct 391 ms 70520 KB Output is correct
39 Correct 411 ms 70972 KB Output is correct
40 Correct 421 ms 70584 KB Output is correct
41 Correct 459 ms 69144 KB Output is correct
42 Correct 433 ms 70972 KB Output is correct
43 Correct 410 ms 68972 KB Output is correct
44 Correct 441 ms 70400 KB Output is correct
45 Correct 382 ms 70224 KB Output is correct
46 Correct 393 ms 70508 KB Output is correct
47 Correct 402 ms 69828 KB Output is correct
48 Correct 406 ms 63424 KB Output is correct
49 Correct 390 ms 67784 KB Output is correct
50 Correct 388 ms 70372 KB Output is correct
51 Correct 384 ms 68300 KB Output is correct
52 Correct 392 ms 69056 KB Output is correct
53 Correct 375 ms 69324 KB Output is correct
54 Correct 393 ms 68760 KB Output is correct
55 Correct 473 ms 68196 KB Output is correct
56 Correct 395 ms 67460 KB Output is correct
57 Correct 400 ms 70188 KB Output is correct
58 Correct 394 ms 69480 KB Output is correct
59 Correct 404 ms 69860 KB Output is correct
60 Correct 419 ms 68328 KB Output is correct
61 Correct 389 ms 69888 KB Output is correct
62 Correct 419 ms 69240 KB Output is correct
63 Correct 359 ms 62628 KB Output is correct
64 Correct 342 ms 62968 KB Output is correct
65 Correct 362 ms 64504 KB Output is correct
66 Correct 347 ms 62632 KB Output is correct
67 Correct 347 ms 62756 KB Output is correct
68 Correct 363 ms 63128 KB Output is correct
69 Correct 348 ms 64176 KB Output is correct
70 Correct 361 ms 63636 KB Output is correct
71 Correct 360 ms 62772 KB Output is correct
72 Correct 343 ms 63612 KB Output is correct
73 Correct 374 ms 63160 KB Output is correct
74 Correct 357 ms 63296 KB Output is correct
75 Correct 369 ms 62984 KB Output is correct
76 Correct 385 ms 63200 KB Output is correct
77 Correct 433 ms 69636 KB Output is correct
78 Correct 478 ms 70776 KB Output is correct
79 Correct 419 ms 70592 KB Output is correct
80 Correct 409 ms 69488 KB Output is correct
81 Correct 442 ms 69256 KB Output is correct
82 Correct 454 ms 70188 KB Output is correct
83 Correct 435 ms 69828 KB Output is correct
84 Correct 435 ms 69196 KB Output is correct
85 Correct 450 ms 70576 KB Output is correct
86 Correct 457 ms 69552 KB Output is correct
87 Correct 407 ms 71160 KB Output is correct
88 Correct 437 ms 71128 KB Output is correct
89 Correct 382 ms 68988 KB Output is correct
90 Correct 421 ms 70620 KB Output is correct
91 Correct 409 ms 69492 KB Output is correct
92 Correct 386 ms 68688 KB Output is correct
93 Correct 434 ms 69960 KB Output is correct
94 Correct 431 ms 71428 KB Output is correct
95 Correct 413 ms 71180 KB Output is correct
96 Correct 395 ms 70044 KB Output is correct
97 Correct 414 ms 69968 KB Output is correct
98 Correct 397 ms 68908 KB Output is correct
99 Correct 423 ms 69844 KB Output is correct
100 Correct 411 ms 70056 KB Output is correct
101 Correct 419 ms 69296 KB Output is correct
102 Correct 453 ms 70676 KB Output is correct