This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
struct node {
std::pair<int, int> x;
int y = rand();
int L = 0, R = 0;
int sz = 1;
int cost = -1e9;
};
const int N = 1e6 + 5;
node t[N];
int cur = 0;
void pull(int v) {
t[v].sz = t[t[v].L].sz + t[t[v].R].sz + 1;
t[v].cost = std::max({t[t[v].L].cost, t[v].x.second - t[t[v].L].sz, t[t[v].R].cost - t[t[v].L].sz - 1});
}
int merge(int v, int u) {
if (!v || !u) return v | u;
if (t[v].y > t[u].y) return t[v].R = merge(t[v].R, u), pull(v), v;
return pull(t[u].L = merge(v, t[u].L)), pull(u), u;
}
std::pair<int, int> split(int v, std::pair<int, int> x) {
if (!v) return {v, v};
if (t[v].x <= x) {
auto [a, b] = split(t[v].R, x);
return t[v].R = a, pull(v), std::pair<int, int>{v, b};
}
auto [a, b] = split(t[v].L, x);
return t[v].L = b, pull(v), std::pair<int, int>{a, v};
}
void add(int&v, std::pair<int, int> x) {
auto [a, b] = split(v, x);
t[++cur].x = x;
pull(cur);
v = merge(merge(a, cur), b);
}
void del(int&v, std::pair<int, int> x) {
auto [a, b] = split(v, x);
auto [y, z] = split(a, {x.first, x.second - 1});
v = merge(y, b);
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
t[0].sz = 0;
std::vector<int> ans(X.size());
int v = 0;
for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
return ans;
}
#ifdef __APPLE__
#include <cstdio>
#include <cstdlib>
#include <vector>
int readInt() {
int i;
if (scanf("%d", &i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return i;
}
int main() {
int N, Q;
N = readInt();
Q = readInt();
std::vector<int> A(N);
for (int i = 0; i < N; i++)
A[i] = readInt();
std::vector<int> X(Q), V(Q);
for (int j = 0; j < Q; j++) {
X[j] = readInt();
V[j] = readInt();
}
std::vector<int> res = countScans(A, X, V);
for (int j = 0; j < int(res.size()); j++)
printf("%d\n", res[j]);
}
#endif
Compilation message (stderr)
bubblesort2.cpp: In function 'std::pair<int, int> split(int, std::pair<int, int>)':
bubblesort2.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [a, b] = split(t[v].R, x);
| ^
bubblesort2.cpp:34:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | auto [a, b] = split(t[v].L, x);
| ^
bubblesort2.cpp: In function 'void add(int&, std::pair<int, int>)':
bubblesort2.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | auto [a, b] = split(v, x);
| ^
bubblesort2.cpp: In function 'void del(int&, std::pair<int, int>)':
bubblesort2.cpp:46:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | auto [a, b] = split(v, x);
| ^
bubblesort2.cpp:47:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | auto [y, z] = split(a, {x.first, x.second - 1});
| ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
| ~~^~~~~~~~~~
bubblesort2.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |