| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 754746 |
2023-06-08T13:30:42 Z |
Pring |
Fire (JOI20_ho_t5) |
C++14 |
|
442 ms |
64144 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 < n; 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
442 ms |
64144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
412 ms |
63212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
62660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
