| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 941137 |
2024-03-08T07:51:54 Z |
atom |
Simple game (IZhO17_game) |
C++17 |
|
9 ms |
35676 KB |
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
struct SegmentTree {
int n;
vector <int> f, lzy;
SegmentTree(int _n) : n(_n), f((_n << 2) + 5), lzy((_n << 2) + 5) {};
int merge(int x, int y) {
return (x + y);
}
void push(int x, int l, int r) {
if (!lzy[x]) return;
int m = (l + r) / 2;
lzy[x << 1] += lzy[x];
f[x << 1] += lzy[x] * (m - l + 1);
lzy[x << 1 | 1] += lzy[x];
f[x << 1 | 1] += lzy[x] * (r - m);
lzy[x] = 0;
}
void upd(int x, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
lzy[x] += val;
f[x] += val * (r - l + 1);
return;
}
int m = (l + r) >> 1;
push(x, l, r);
upd(x << 1, l, m, u, v, val);
upd(x << 1 | 1, m + 1, r, u, v, val);
f[x] = merge(f[x << 1], f[x << 1 | 1]);
}
int qry(int x, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return f[x];
int m = (l + r) >> 1;
push(x, l, r);
int ql = qry(x << 1, l, m, u, v);
int qr = qry(x << 1 | 1, m + 1, r, u, v);
return merge(ql, qr);
}
void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); }
int qry(int l, int r) { return qry(1, 1, n, l, r); }
};
const int N = 1e6 + 5;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector <int> h(n + 5);
vector <vector <int>> queries(q + 5);
for (int i = 1; i <= n; ++i) cin >> h[i];
bool sub2 = 1;
for (int i = 1; i <= q; ++i) {
int cmd; cin >> cmd;
if (cmd == 1) {
int x, y; cin >> x >> y;
queries[i] = {cmd, x, y};
sub2 = 0;
}
else {
int x; cin >> x;
queries[i] = {cmd, x};
}
}
// sub1
// if (n <= 1000 && q <= 1000) {
// vector <int> cnt(N, 0);
// for (int i = 1; i <= n; ++i) cnt[h[i]]++;
// for (int i = 1; i <= q; ++i) {
// if (queries[i][0] == 1) {
// cnt[h[queries[i][1]]]--;
// h[queries[i][1]] = queries[i][2];
// cnt[h[queries[i][1]]]++;
// }
// else {
// int ans = 0;
// int H = queries[i][1];
// for (int j = 2; j <= n; ++j)
// if ((h[j - 1] < H && H < h[j]) || (h[j - 1] > H && H > h[j]))
// ++ans;
// cout << ans << "\n";
// }
// }
// }
// else if (sub2) {
// // Fenwick
// vector <int> cnt(N);
// vector <int> prf(N);
// for (int i = 1; i <= n; ++i)
// cnt[h[i]]++;
// for (int i = 2; i <= n; ++i) {
// int l = h[i - 1], r = h[i];
// if (l > r) swap(l, r);
// l++, r--;
// if (l <= r) {
// prf[l]++;
// prf[r + 1]--;
// }
// }
// for (int i = 1; i < N; ++i) prf[i] += prf[i - 1];
// for (int i = 1; i <= q; ++i) {
// cout << (cnt[queries[i][1]] + prf[queries[i][1]]) << "\n";
// }
// }
// else
// {
vector <int> cnt(N);
SegmentTree st(N);
for (int i = 1; i <= n; ++i) cnt[h[i]]++;
for (int i = 2; i <= n; ++i) {
int l = h[i - 1], r = h[i];
if (l > r) swap(l, r);
l++, r--;
st.upd(l, r, 1);
}
for (int i = 1; i <= q; ++i) {
// debug(queries[i]);
int cmd = queries[i][0];
int x, y;
if (cmd == 1) {
x = queries[i][1]; y = queries[i][2];
cnt[h[x]]--;
if (i > 1) {
int l = h[i - 1], r = h[i];
if (l > r) swap(l, r);
st.upd(l + 1, r - 1, -1);
}
if (i < n) {
int l = h[i], r = h[i + 1];
if (l > r) swap(l, r);
st.upd(l + 1, r - 1, -1);
}
h[x] = y;
cnt[h[x]]++;
if (i > 1) {
int l = h[i - 1], r = h[i];
if (l > r) swap(l, r);
st.upd(l + 1, r - 1, 1);
}
if (i < n) {
int l = h[i], r = h[i + 1];
if (l > r) swap(l, r);
st.upd(l + 1, r - 1, 1);
}
}
else {
x = queries[i][1];
ll ans = cnt[x] + st.qry(x, x);
cout << ans << "\n";
}
// }
}
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:68:10: warning: variable 'sub2' set but not used [-Wunused-but-set-variable]
68 | bool sub2 = 1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35676 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
35604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35676 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
35604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35676 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
35604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
