oj.uz

답안 #754751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754751 2023-06-08T13:36:21 Z Pring Fire (JOI20_ho_t5) C++14
6 / 100
 514 ms 68624 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--;
    }
    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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 444 ms 64256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 455 ms 63384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 396 ms 62624 KB Output is correct
2 Correct 391 ms 66976 KB Output is correct
3 Correct 469 ms 68624 KB Output is correct
4 Correct 401 ms 66652 KB Output is correct
5 Correct 397 ms 66996 KB Output is correct
6 Correct 391 ms 67160 KB Output is correct
7 Correct 405 ms 68300 KB Output is correct
8 Correct 394 ms 67744 KB Output is correct
9 Correct 451 ms 66904 KB Output is correct
10 Correct 426 ms 67900 KB Output is correct
11 Correct 454 ms 67312 KB Output is correct
12 Correct 452 ms 67492 KB Output is correct
13 Correct 447 ms 67188 KB Output is correct
14 Correct 514 ms 67432 KB Output is correct

Subtask #5
0 / 80.0

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