| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 856624 |
2023-10-04T05:51:29 Z |
overwatch9 |
Sails (IOI07_sails) |
C++17 |
|
157 ms |
7464 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int maxn = 1e5;
struct stree {
#define lc v*2
#define rc v*2+1
vector <int> tree;
stree (int sz) {
tree = vector <int> (sz*4);
}
void pushup(int v) {
if (tree[lc] == 0)
tree[v] = tree[rc];
else
tree[v] = tree[lc];
}
void update(int v, int tl, int tr, int p, int val) {
if (tl > p || tr < p)
return;
if (tl == tr) {
tree[v] += val;
return;
}
int tm = (tl + tr) / 2;
update(lc, tl, tm, p, val);
update(rc, tm+1, tr, p, val);
pushup(v);
}
int query(int v, int tl, int tr, int p) {
if (tl > p || tr < p)
return 0;
if (tl == tr)
return tree[v];
int tm = (tl + tr) / 2;
int a = query(lc, tl, tm, p);
if (a == 0)
return query(rc, tm+1, tr, p);
return 0;
}
// find index of leftmost value in the range l->r that is non zero
int queryl(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl == tr)
return tree[v];
int tm = (tl + tr) / 2;
if (tl == tm && tm >= l) {
if (tree[lc] != 0)
return tl;
return 0;
}
int a = queryl(lc, tl, tm, l, r);
if (a != 0)
return a;
if (tm+1 == tr && tr <= r) {
if (tree[rc] != 0)
return tr;
return 0;
}
a = queryl(rc, tm+1, tr, l, r);
if (a != 0)
return a;
return 0;
}
// find index of rightmost value in the range l->r that is non zero
int queryr(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl >= l && tr <= r) {
if (tree[v] != 0)
return tr;
return 0;
}
int tm = (tl + tr) / 2;
if (tm+1 == tr && tm+1 <= r) {
if (tree[rc] != 0)
return tr;
return 0;
}
int a = queryr(rc, tm+1, tr, l, r);
if (a != 0)
return a;
if (tl == tm && tm >= l) {
if (tree[lc] != 0)
return tl;
return 0;
}
a = queryr(lc, tl, tm, l, r);
if (a != 0)
return a;
return 0;
}
};
struct node {
int val = 0, pd = 0;
bool up = false;
};
struct stree2 {
#define lc v*2
#define rc v*2+1
vector <node> tree;
stree2 (int sz) {
tree = vector <node> (sz*4);
}
void pushdown(int v, int tl, int tm, int tr) {
if (!tree[v].up)
return;
tree[v].up = false;
tree[lc].up = tree[rc].up = true;
tree[lc].pd += tree[v].pd;
tree[rc].pd += tree[v].pd;
tree[lc].val += (tm - tl + 1);
tree[rc].val += (tr - tm);
tree[v].pd = 0;
}
void update(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l || l > r)
return;
if (tl >= l && tr <= r) {
tree[v].pd++;
tree[v].up = true;
tree[v].val += (tr - tl + 1);
return;
}
int tm = (tl + tr) / 2;
pushdown(v, tl, tm, tr);
update(lc, tl, tm, l, r);
update(rc, tm+1, tr, l, r);
}
int query(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl >= l && tr <= r)
return tree[v].val;
int tm = (tl + tr) / 2;
pushdown(v, tl, tm, tr);
int a = query(lc, tl, tm,l, r);
int b = query(rc, tm+1, tr,l, r);
return a + b;
}
};
int main() {
int n;
cin >> n;
vector <pair <int, int>> updates(n);
for (int i = 0; i < n; i++)
cin >> updates[i].first >> updates[i].second;
sort(updates.begin(), updates.end());
stree tree(maxn + 5);
stree2 tree2(maxn + 5);
int r = 0;
ll ans = 0;
for (int i = 0; i < n; i++) {
r = max(r, updates[i].first + 1);
int k = updates[i].second;
int v = tree.query(1, 0, maxn + 4, r - k - 1);
ll res = tree2.query(1, 0, maxn + 4, r - k-1, r-2);
ans += res;
if (k == r) {
tree.update(1, 0, maxn + 4, 0, 1);
tree2.update(1, 0, maxn + 4, 0, r-2);
} else if (v == 0) {
int lb = tree.queryr(1, 0, maxn + 4, 0, r - k - 1);
int rb = r-2;
int rx = lb + k - 1;
int lx = max(rx+2, tree.queryl(1, 0, maxn + 4, rx, rb));
tree.update(1, 0, maxn + 4, lb, 1);
tree.update(1, 0, maxn + 4, rx+1, -1);
tree.update(1, 0, maxn + 4, lx, 1);
tree2.update(1, 0, maxn + 4, lb, rx);
if (lx > rx && lx <= rb)
tree2.update(1, 0, maxn + 4, lx, rb);
} else {
int lb = tree.queryr(1, 0, maxn + 4, 0, r - k - 1);
int rb = r-2;
tree.update(1, 0, maxn + 4, lb, 1);
tree2.update(1, 0, maxn + 4, lb, rb);
}
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
6800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
7248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
7284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
7464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
