| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 559994 |
2022-05-11T02:38:48 Z |
two_sides |
Fish 2 (JOI22_fish2) |
C++17 |
|
62 ms |
30812 KB |
#include <bits/stdc++.h>
using namespace std;
#define il i + 1
#define ir i + (m - l + 1) * 2
using ll = long long;
struct item {
int pos, cnt; ll sum;
item(int pos, int cnt, ll sum):
pos(pos), cnt(cnt), sum(sum) {}
};
struct node {
vector<item> lef, rig;
};
const int N = 100005;
int val[N]; node seg[N * 2];
node res; int lo, hi;
void merge(int m, node a, node b, node &c) {
c.lef.clear(); c.rig.clear();
for (auto u : a.lef)
if (u.sum < val[u.pos + 1])
c.lef.push_back(u);
for (auto u : b.rig)
if (u.sum < val[u.pos - 1])
c.rig.push_back(u);
for (int i = 0, j = 0; i < a.rig.size(); i++) {
while (j < b.lef.size() && a.rig[i].sum +
(j ? b.lef[j - 1].sum : 0) >=
val[j ? b.lef[j - 1].pos + 1 : m + 1]) j++;
if (j && i + 1 < a.rig.size() &&
a.rig[i].sum + b.lef[j - 1].sum >=
val[a.rig[i].pos - 1]) {
a.rig[i + 1].cnt += a.rig[i].cnt;
continue;
}
if (j == b.lef.size()) {
item u = a.rig[i];
u.sum += b.lef[j - 1].sum;
c.rig.push_back(u);
}
}
for (int i = 0, j = 0; i < b.lef.size(); i++) {
while (j < a.rig.size() && b.lef[i].sum +
(j ? a.rig[j - 1].sum : 0) >=
val[j ? a.rig[j - 1].pos - 1 : m]) j++;
if (j && i + 1 < b.lef.size() &&
b.lef[i].sum + a.rig[j - 1].sum >=
val[b.lef[i].pos + 1]) {
b.lef[i + 1].cnt += b.lef[i].cnt;
continue;
}
if (j == a.rig.size()) {
item u = b.lef[i];
u.sum += a.rig[j - 1].sum;
c.lef.push_back(u);
}
}
if (c.lef.empty() || c.lef.back().pos != b.lef.back().pos)
c.lef.push_back(c.rig.back());
else if (c.rig.empty() || c.rig.back().pos != a.rig.back().pos)
c.rig.push_back(c.lef.back());
else c.lef.back().cnt = c.rig.back().cnt
= c.lef.back().cnt + c.rig.back().cnt;
c.lef.back().pos = b.lef.back().pos;
c.rig.back().pos = a.rig.back().pos;
}
void build(int i, int l, int r) {
if (l == r) {
seg[i].lef.emplace_back(l, 1, val[l]);
seg[i].rig.emplace_back(l, 1, val[l]);
} else {
int m = (l + r) / 2;
build(il, l, m); build(ir, m + 1, r);
merge(m, seg[il], seg[ir], seg[i]);
// cerr<<l<<' '<<m<<' '<<r<<'\n';
// for (auto u : seg[i].lef)
// cerr<<u.pos<<' '<<u.cnt<<'\n';
// cerr<<'\n';
// for (auto u : seg[i].rig)
// cerr<<u.pos<<' '<<u.cnt<<'\n';
// cerr<<'\n';
}
}
void update(int i, int l, int r, int p) {
if (l == r) {
seg[i].lef[0] = {l, 1, val[l]};
seg[i].rig[0] = {l, 1, val[l]};
} else {
int m = (l + r) / 2;
if (m >= p) update(il, l, m, p);
else update(ir, m + 1, r, p);
merge(m, seg[il], seg[ir], seg[i]);
}
}
void get(int i, int l, int r) {
if (l >= lo && r <= hi) {
if (l == lo) res = seg[i];
else merge(l - 1, res, seg[i], res);
} else {
int m = (l + r) / 2;
if (m >= lo) get(il, l, m);
if (m < hi) get(ir, m + 1, r);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> val[i];
build(1, 1, n);
int q; cin >> q;
while (q--) {
int cmd; cin >> cmd;
if (cmd == 1) {
int p; cin >> p >> val[p];
update(1, 1, n, p);
} else {
cin >> lo >> hi; get(1, 1, n);
cout << res.lef.back().cnt << '\n';
}
}
}
Compilation message
fish2.cpp: In function 'void merge(int, node, node, node&)':
fish2.cpp:36:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0, j = 0; i < a.rig.size(); i++) {
| ~~^~~~~~~~~~~~~~
fish2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (j < b.lef.size() && a.rig[i].sum +
| ~~^~~~~~~~~~~~~~
fish2.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (j && i + 1 < a.rig.size() &&
| ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if (j == b.lef.size()) {
| ~~^~~~~~~~~~~~~~~
fish2.cpp:52:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0, j = 0; i < b.lef.size(); i++) {
| ~~^~~~~~~~~~~~~~
fish2.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (j < a.rig.size() && b.lef[i].sum +
| ~~^~~~~~~~~~~~~~
fish2.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (j && i + 1 < b.lef.size() &&
| ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (j == a.rig.size()) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
30812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
30812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
30812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
