/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 1e6+2e5+23, lg = 20;
ll Mod = 1e9+7; //998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
int n, q, a[N], seg[3*N], lazy[3*N];
set<int> st[N];
vector<int> comp;
int get(int x) {
int ptr = lower_bound(all(comp), x) - comp.begin() + 1;
return ptr;
}
inline void pushdown(int ind) {
seg[ind] += lazy[ind];
(ind<(1<<lg)) && (lazy[2*ind] += lazy[ind]);
(ind<(1<<lg)) && (lazy[2*ind+1] += lazy[ind]);
lazy[ind] = 0;
}
void update(int l, int r, int y, int ind=1, int lc=1, int rc=(1<<lg)+1) {
pushdown(ind);
if(l>=rc || lc>=r) return;
if(lc>=l && rc<=r) {
lazy[ind] += y;
pushdown(ind);
return;
}
int mid = (lc+rc)/2;
update(l, r, y, 2*ind, lc, mid);
update(l, r, y, 2*ind+1, mid, rc);
seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}
void update2(int pos, int y, int ind=1, int lc=1, int rc=(1<<lg)+1) {
pushdown(ind);
if(ind>=(1<<lg)) {
seg[ind] = y;
return;
}
int mid = (lc+rc)/2;
if(pos<mid) update2(pos, y, 2*ind, lc, mid);
else update2(pos, y, 2*ind+1, mid, rc);
seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}
int fen[N];
void ufen(int x, int val) {
while(x < N) {
fen[x] += val; x += (x&(-x));
}
}
int qfen(int pos) {
int res = 0;
while(pos > 0) {
res += fen[pos]; pos -= (pos&(-pos));
}
return res;
}
int query(int x, int ind=1, int lc=1, int rc=(1<<lg)+1) {
pushdown(ind);
if(ind >= (1<<lg)) return seg[ind];
int mid = (lc+rc)/2;
if(x < mid) return query(x, 2*ind, lc, mid);
return query(x, 2*ind+1, mid, rc);
}
vector<int> countScans (vector<int> A, vector<int> X, vector<int> V) {
n=size(A), q=size(X);
for(int i=1; i<=n; i++) comp.pb(A[i-1]);
for(int i=1; i<=q; i++) comp.pb(V[i-1]), X[i-1]++;
sort(all(comp));
comp.resize(unique(all(comp)) - comp.begin());
for(int i=1; i<=n; i++) a[i] = get(A[i-1]), ufen(a[i], 1);
for(int i=1; i<=q; i++) V[i-1] = get(V[i-1]);
vector<int> ans;
for(int i=1; i<=n+q; i++) st[i].insert(0);
for(int i=1; i<=n; i++) {
update2(a[i], max(i-qfen(a[i]), query(a[i])));
st[a[i]].insert(i);
}
for(int x,v,i=1; i<=q; i++) {
x=X[i-1], v=V[i-1];
st[a[x]].erase(x);
update(1, a[x]+1, -1);
st[v].insert(x);
update(1, v+1, 1);
ufen(a[x], -1); ufen(v, 1);
update2(a[x], (*st[a[x]].rbegin())-qfen(a[x]));
a[x] = v;
update2(a[x], (*st[a[x]].rbegin())-qfen(a[x]));
ans.pb(seg[1]);
}
return ans;
}
/*
int main() {
vector<int> ans = countScans({1, 1, 2, 2}, {0, 3}, {3, 3});
for(auto it : ans) cout<<it<<endl;
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
68184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
68184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
71248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
68184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
