| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 817137 |
2023-08-09T09:47:03 Z |
GEN 이지후(#10378) |
Ants and Sugar (JOI22_sugar) |
C++17 |
|
889 ms |
127368 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXT = 1050000;
struct bit {
lint tree[MAXT];
void add(int x, lint v) {
for (int i = x + 2; i < MAXT; i += i & -i)
tree[i] += v;
}
lint query(int x) {
lint ret = 0;
for (int i = x + 2; i; i -= i & -i)
ret += tree[i];
return ret;
}
} bit;
lint l;
vector<lint> vect;
struct node {
lint adj[3][3], lazy;
node() {
lazy = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
adj[i][j] = -1e18;
}
}
}
void addLazy(lint x, int pos) {
lazy += x;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (j == 0)
continue;
if (i > 0 && j == 2)
continue;
adj[i][j] -= x;
}
}
}
node operator+(const node &nd) const {
node ret;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
ret.adj[j][k] = max(ret.adj[j][k], adj[j][i] + nd.adj[i][k]);
}
}
}
return ret;
}
} tree[MAXT];
void init(int s, int e, int p, vector<node> &v) {
if (s == e) {
tree[p] = v[s];
return;
}
int m = (s + e) / 2;
init(s, m, 2 * p, v);
init(m + 1, e, 2 * p + 1, v);
tree[p] = tree[2 * p] + tree[2 * p + 1];
}
void lazydown(int p, int ps, int pm) {
if (tree[p].lazy) {
for (int i = 2 * p; i < 2 * p + 2; i++) {
tree[i].addLazy(tree[p].lazy, (i % 2 ? (pm + 1) : ps));
}
tree[p].lazy = 0;
}
}
void upd(int pos, int s, int e, int p, node v) {
if (s == e) {
tree[p] = v;
return;
}
int m = (s + e) / 2;
lazydown(p, s, m);
if (pos <= m)
upd(pos, s, m, 2 * p, v);
else
upd(pos, m + 1, e, 2 * p + 1, v);
tree[p] = tree[2 * p] + tree[2 * p + 1];
}
void lazy(int s, int e, int ps, int pe, int p, lint v) {
if (e < ps || pe < s)
return;
if (s <= ps && pe <= e) {
tree[p].addLazy(v, ps);
return;
}
int pm = (ps + pe) / 2;
lazydown(p, ps, pm);
lazy(s, e, ps, pm, 2 * p, v);
lazy(s, e, pm + 1, pe, 2 * p + 1, v);
tree[p] = tree[2 * p] + tree[2 * p + 1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
lint q;
cin >> q >> l;
vector<array<lint, 3>> qry(q);
for (int i = 0; i < q; i++) {
for (int j = 0; j < 3; j++) {
cin >> qry[i][j];
}
if (qry[i][0] == 1) {
qry[i][1] -= l;
}
if (qry[i][0] == 2)
vect.push_back(qry[i][1]);
}
if (sz(vect) == 0) {
while (q--)
cout << "0\n";
return 0;
}
sort(all(vect));
vect.resize(unique(all(vect)) - vect.begin());
// (my weight, R mode, T mode)
vector<array<lint, 2>> values(sz(vect));
auto genNode = [&](int pos) {
node ret;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (j == 0)
ret.adj[i][j] = 0;
if (j == 1)
if (i == 0)
ret.adj[i][j] = values[pos][0] - bit.query(pos);
if (j == 2) {
if (i > 0 && (pos > 0 && vect[pos] - vect[pos - 1] <= 2 * l)) {
ret.adj[i][j] = values[pos][0] - values[pos][1];
} else
ret.adj[i][j] = -1e18;
}
}
}
return ret;
};
vector<node> nodes;
for (int i = 0; i < sz(vect); i++) {
nodes.push_back(genNode(i));
}
init(0, sz(vect) - 1, 1, nodes);
lint sugsum = 0;
for (int i = 0; i < q; i++) {
if (qry[i][0] == 1) {
int st = lower_bound(all(vect), qry[i][1]) - vect.begin();
int ed = lower_bound(all(vect), qry[i][1] + 2 * l + 1) - vect.begin();
if (st < sz(vect)) {
values[st][1] += qry[i][2];
upd(st, 0, sz(vect) - 1, 1, genNode(st));
}
if (st < ed) {
bit.add(st, qry[i][2]);
bit.add(ed, -qry[i][2]);
lazy(st + 1, ed - 1, 0, sz(vect) - 1, 1, qry[i][2]);
upd(st, 0, sz(vect) - 1, 1, genNode(st));
}
} else {
auto it = lower_bound(all(vect), qry[i][1]) - vect.begin();
values[it][0] += qry[i][2];
sugsum += qry[i][2];
upd(it, 0, sz(vect) - 1, 1, genNode(it));
}
cout << sugsum - *max_element(tree[1].adj[0], tree[1].adj[0] + 3) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
82516 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
82544 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
82552 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
82508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
82520 KB |
Output is correct |
| 2 |
Correct |
375 ms |
102516 KB |
Output is correct |
| 3 |
Correct |
506 ms |
115128 KB |
Output is correct |
| 4 |
Correct |
820 ms |
127368 KB |
Output is correct |
| 5 |
Correct |
859 ms |
127276 KB |
Output is correct |
| 6 |
Incorrect |
889 ms |
117844 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
82516 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
82544 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
