oj.uz

Submission #754787

# Submission time Handle Problem Language Result Execution time Memory
754787 2023-06-08T14:14:58 Z Pring Fire (JOI20_ho_t5) C++14
6 / 100
 435 ms 64548 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() {
    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 435 ms 64212 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 421 ms 63420 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 365 ms 62604 KB Output is correct
2 Correct 369 ms 63052 KB Output is correct
3 Correct 359 ms 64548 KB Output is correct
4 Correct 373 ms 62540 KB Output is correct
5 Correct 391 ms 62760 KB Output is correct
6 Correct 340 ms 63108 KB Output is correct
7 Correct 363 ms 64124 KB Output is correct
8 Correct 361 ms 63660 KB Output is correct
9 Correct 354 ms 62732 KB Output is correct
10 Correct 426 ms 63732 KB Output is correct
11 Correct 370 ms 63340 KB Output is correct
12 Correct 375 ms 63404 KB Output is correct
13 Correct 360 ms 63152 KB Output is correct
14 Correct 364 ms 63220 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 -