#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
const int INF = 1000 * 1000;
struct Seg {
int n;
vi add, mx;
Seg(int n, vi &vals): n(n) {
add.assign(4 * n, 0);
mx.assign(4 * n, 0);
build(vals);
}
void propagate(int v, int tl, int tr) {
if(tl == tr || add[v] == 0)
return;
add[2 * v] += add[v];
add[2 * v + 1] += add[v];
mx[2 * v] += add[v];
mx[2 * v + 1] += add[v];
add[v] = 0;
}
void pull(int v) {
mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void build(vi &vals, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
if(tl == tr) {
mx[v] = vals[tl];
return;
}
int tm = (tl + tr) / 2;
build(vals, 2 * v, tl, tm);
build(vals, 2 * v + 1, tm + 1, tr);
pull(v);
}
void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
propagate(v, tl, tr);
if(l > r) return;
if(tl == l && r == tr) {
add[v] = val;
mx[v] += val;
return;
}
int tm = (tl + tr) / 2;
update(l, min(r, tm), val, 2 * v, tl, tm);
update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr);
pull(v);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
propagate(v, tl, tr);
if(l > r) return -INF;
if(tl == l && r == tr)
return mx[v];
int tm = (tl + tr) / 2;
int ql = query(l, min(r, tm), 2 * v, tl, tm);
int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);
return max(ql, qr);
}
int get_max() {
return query(0, n - 1);
}
int at(int p) {
return query(p, p);
}
void set(int p, int nval) {
update(p, p, nval - at(p));
}
};
struct Seg2 {
int n;
vi t;
Seg2(int n): n(n) {
t.resize(2 * n);
}
void set(int p, int val) {
for(t[p += n] = val; p > 1; p /= 2)
t[p >> 1] = t[p] + t[p ^ 1];
}
int sum(int l, int r) {
int res = 0;
for(l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if(l & 1) res += t[l++];
if(r & 1) res += t[--r];
}
return res;
}
int at(int p) {
return sum(0, p) - sum(0, p - 1);
}
};
vi countScans(vi a, vi xs, vi vs) {
int n = sz(a);
int q = sz(xs);
set<ii> s;
vii vals;
forn(i, n) {
s.insert({a[i], i});
vals.eb(a[i], i);
}
forn(i, q) {
s.insert({vs[i], xs[i]});
}
map<ii, int> p2ind;
int ct = 0;
for(ii el: s) {
p2ind[el] = ct++;
// cerr << p2ind[el] << ' ';
} //cerr << endl;
int N = sz(s);
sort(all(vals));
vi seg_vals(N, -INF);
Seg2 sl(N);
// forn(i, N) {
// cout << sl.at(i) << ' ';
// } cout << endl;
forn(i, n) {
int ind = p2ind[vals[i]];
seg_vals[ind] = vals[i].S - i;
// cout << ind << endl;
sl.set(ind, 1);
}
Seg seg(N, seg_vals);
vi ans(q);
// forn(i, N) {
// cout << sl.at(i) << ' ';
// } cout << endl;
forn(i, q) {
int x = xs[i], v = vs[i];
int ind_fr = p2ind[{a[x], x}];
int ind_to = p2ind[{v, x}];
sl.set(ind_fr, 0);
sl.set(ind_to, 1);
if(ind_to > ind_fr) {
seg.update(ind_fr, ind_to, 1);
}
if(ind_to < ind_fr) {
seg.update(ind_to, ind_fr, -1);
}
if(ind_to != ind_fr) {
int rem = x - sl.sum(0, ind_to - 1);
seg.set(ind_fr, -INF);
seg.set(ind_to, rem);
}
a[x] = v;
ans[i] = seg.get_max();
//
// forn(i, N) {
// cout << sl.at(i) << ' ';
// } cout << endl;
}
return ans;
}
void solve() {
int n, q;
cin >> n >> q;
vi a(n);
forn(i, n)
cin >> a[i];
vi xs, vs;
forn(_, q) {
int x, v;
cin >> x >> v;
xs.pb(x);
vs.pb(v);
}
vi ans = countScans(a, xs, vs);
for(int a: ans)
cout << a << endl;
}
//int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
//// cout.tie(nullptr);
//
//// freopen("optmilk.in", "r", stdin);
//// freopen("optmilk.out", "w", stdout);
//
// int t = 1;
//// cin >> t;
// while(t--) {
// solve();
// }
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
5272 KB |
Output is correct |
| 2 |
Correct |
124 ms |
11148 KB |
Output is correct |
| 3 |
Incorrect |
272 ms |
17208 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
