/*
(1)(number x: x < i && a[x] > a[i])
(2)(i - number x: a[x] < a[i])
(1) >= (2) -> res = max((2))
*/
#include "bubblesort2.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb emplace_back
#define mp make_pair
using namespace std;
const int N = int(1e5) + 2;
typedef pair<int, int> pii;
struct TSegment {
vector<int> st, lazy, l, h;
void Init(int n) { ++n;
st.resize(n << 2, 0), lazy.resize(n << 2, 0);
l.resize(n << 2, 0), h.resize(n << 2, 0);
}
void Build(int x, int low, int high) {
l[x] = low, h[x] = high;
if(l[x] == h[x]) {st[x] = 0; return;}
int mid = (low + high) >> 1;
Build(x << 1, low, mid);
Build(x << 1 | 1, mid + 1, high);
st[x] = max(st[x << 1], st[x << 1 | 1]);
}
void Down(int x) {
if(!lazy[x]) return;
st[x] += lazy[x];
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
lazy[x] = 0;
}
void Update(int x, int low, int high, int val) {
if(high > low || l[x] > high || h[x] < low) return;
if(l[x] >= low && h[x] <= high) {
lazy[x] += val; Down(x);
return;
}
Down(x);
Update(x << 1, low, high, val);
Update(x << 1 | 1, low, high, val);
st[x] = max(st[x << 1], st[x << 1 | 1]);
}
int Query() {Down(1); return st[1];}
} Irene;
vector<pii> v;
int sz, p;
void Add(int val, int x) {
p = lower_bound(v.begin(), v.end(), mp(val, x)) - v.begin() + 1;
Irene.Update(1, p, p, x);
Irene.Update(1, p + 1, sz, -1);
}
void Rmv(int val, int x) {
p = lower_bound(v.begin(), v.end(), mp(val, x)) - v.begin() + 1;
Irene.Update(1, p, p, -x);
Irene.Update(1, p + 1, sz, 1);
}
vector<int> countScans(vector<int> a, vector<int> qx, vector<int> qv) {
int n = a.size(), q = qx.size(); vector<int> res;
for(int i = 0; i < n; ++i) v.pb(a[i], i);
for(int i = 0; i < q; ++i) v.pb(qv[i], qx[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()));
Irene.Init(sz = v.size()); Irene.Build(1, 1, sz);
for(int i = 0; i < n; ++i) Add(a[i], i);
for(int i = 0; i < q; ++i) {
Rmv(a[qx[i]], qx[i]); Add(qv[i], qx[i]);
a[qx[i]] = qv[i];
res.pb(Irene.Query());
}
return res;
}
//
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// if(fopen("test.inp", "r")) {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// }
// int n, q; vector<int> a, v, x, res;
// cin >> n >> q; a.resize(n);
// for(int& x: a) cin >> x;
// x.resize(q), v.resize(q);
// for(int i = 0; i < q; ++i) cin >> x[i] >> v[i];
// res = countScans(a, x, v);
// for(int ans: res) cout << ans << '\n';
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
