/*
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;
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 seg2[3*N];
void upd(int ind, int val) {
if(ind==0) return;
if(ind>=(1<<lg)) seg2[ind]=val;
else seg2[ind] = max(seg2[2*ind], seg2[2*ind+1]);
upd(ind/2, val);
}
int fnd(int val, int ind=1, int lc=1, int rc=(1<<lg)+1) {
if(ind >= (1<<lg)) return lc;
int mid = (lc+rc)/2;
if(seg2[2*ind] >= val) return fnd(val, 2*ind, lc, mid);
return fnd(val, 2*ind+1, mid, rc);
}
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 main () {
cin>>n>>q;
vector<int> A(n), V(q), X(q);
for(int i=1; i<=n; i++) cin>>A[i-1];
for(int i=1; i<=q; i++) cin>>X[i-1]>>V[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]);
for(int i=1; i<=q; i++) V[i-1] = get(V[i-1]);
int mn = 1e9+1;
for(int i=n; i>=1; i--) {
if(a[i] < mn) {
st.insert(i); mn = a[i];
upd(i+(1<<lg)-1, a[i]);
} else {
update2(i+(1<<lg)-1, -n-1);
}
if (a[i] > mn) {
int pos = fnd(a[i]);
update(i, pos+1, 1);
}
ufen(a[i], 1);
}
vector<int> ans;
for(int pos,x,v,i=1; i<=q; i++) {
x=X[i-1], v=V[i-1];
ufen(a[x], -1);
ufen(v, 1);
if(st.find(x) != st.end()) {
update2(x+(1<<lg)-1, -n);
st.erase(x);
} else {
pos = max(fnd(a[x]), x);
update(x, pos, -1);
}
a[x] = v;
st.insert(x);
upd(x+(1<<lg)-1, a[x]);
vector<int> vec;
while(size(st) > 0) {
auto it = st.lower_bound(x);
if(it==st.begin()) break;
it--;
if(a[(*it)] >= a[x]) {
update2((*it), -n);
upd((*it)+(1<<lg)-1, 0);
st.erase((*it));
} else break;
}
auto it = st.lower_bound(x);
it++;
if(it==st.end() || a[(*it)] > a[x]) {
update2(x, qfen(N-1) - qfen(a[x]) - (n-x));
} else {
upd(x+(1<<lg)-1, 0);
st.erase(x);
int pos = max(x, fnd(a[x]));
update(x, pos, 1);
}
cout<<seg[1]<<endl;
}
return 0;
}
*/
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]);
for(int i=1; i<=q; i++) V[i-1] = get(V[i-1]);
vector<int> ans;
int mn = 1e9+1;
for(int i=n; i>=1; i--) {
if(a[i] < mn) {
st.insert(i); mn = a[i];
upd(i+(1<<lg)-1, a[i]);
} else {
update2(i+(1<<lg)-1, -n-1);
}
if (a[i] > mn) {
int pos = fnd(a[i]);
update(i, pos+1, 1);
}
ufen(a[i], 1);
}
for(int pos,x,v,i=1; i<=q; i++) {
x=X[i-1], v=V[i-1];
ufen(a[x], -1);
ufen(v, 1);
if(st.find(x) != st.end()) {
update2(x+(1<<lg)-1, -n);
st.erase(x);
} else {
pos = max(fnd(a[x]), x);
update(x, pos, -1);
}
a[x] = v;
st.insert(x);
upd(x+(1<<lg)-1, a[x]);
vector<int> vec;
while(size(st) > 0) {
auto it = st.lower_bound(x);
if(it==st.begin()) break;
it--;
if(a[(*it)] >= a[x]) {
update2((*it), -n);
upd((*it)+(1<<lg)-1, 0);
st.erase((*it));
} else break;
}
auto it = st.lower_bound(x);
it++;
if(it==st.end() || a[(*it)] > a[x]) {
update2(x, qfen(N-1) - qfen(a[x]) - (n-x));
} else {
upd(x+(1<<lg)-1, 0);
st.erase(x);
int pos = max(x, fnd(a[x]));
update(x, pos, 1);
}
ans.pb(seg[1]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
29784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
