oj.uz

Submission #754783

# Submission time Handle Problem Language Result Execution time Memory
754783 2023-06-08T14:08:40 Z Pring Fire (JOI20_ho_t5) C++14
6 / 100
 488 ms 68620 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;

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;

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() {
    B[0].init(n);
    B[1].init(n);
    B[2].init(n);
    B[3].init(n);
    B[4].init(n);
    B[5].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();
        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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 444 ms 64368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 436 ms 63340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 66644 KB Output is correct
2 Correct 401 ms 67016 KB Output is correct
3 Correct 447 ms 68620 KB Output is correct
4 Correct 465 ms 66736 KB Output is correct
5 Correct 438 ms 66900 KB Output is correct
6 Correct 406 ms 67152 KB Output is correct
7 Correct 455 ms 68276 KB Output is correct
8 Correct 442 ms 67772 KB Output is correct
9 Correct 399 ms 66896 KB Output is correct
10 Correct 488 ms 67656 KB Output is correct
11 Correct 396 ms 67404 KB Output is correct
12 Correct 440 ms 67656 KB Output is correct
13 Correct 382 ms 67204 KB Output is correct
14 Correct 456 ms 67528 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -