#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
const int N = 1e6+5;
const ll mod = 998244353;
const int base = 300;
ll m, n, t, k, d[N], a[N], b[N], id[N], c[N], ans, tong, st[N*4], lazy[N*4], fe[N], sz;
vector<pll> adj[N];
vector<ll> kq;
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n & 1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
ll lwr(ll x)
{
return lower_bound(kq.begin(), kq.end(), x) - kq.begin() + 1;
}
string s;
void add(ll id, ll x)
{
for(; id <= sz; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
ll total = 0;
for(; id; id -= id & -id)total += fe[id];
return total;
}
set<ll> val[N];
void down(ll id)
{
if(!lazy[id])return;
st[id*2] += lazy[id];
st[id*2+1] += lazy[id];
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll x)
{
if(u <= l && r <= v)
{
if(u == v)st[id] = x;
else
{
st[id] += x;
lazy[id] += x;
}
return;
}
if(u > v || u > r || l > v)return;
ll mid = (l + r) / 2;
down(id);
update(id*2, l, mid, u, v, x);
update(id*2+1, mid+1, r, u, v, x);
st[id] = max(st[id*2], st[id*2+1]);
}
void cal(ll x)
{
if(val[x].empty())update(1, 1, n, x, x, -mod);
else
{
k = (*val[x].rbegin()) - get(x);
update(1, 1, n, x, x, k);
}
}
vector<ll> countScans(vector<ll> A, vector<ll> X, vector<ll> V)
{
//cin >> n >> m;
n = A.size();
m = X.size();
for(int i = 1; i <= n; i ++)
{
a[i] = A[i-1];
//cin >> a[i];
kq.pb(a[i]);
}
for(int i = 1; i <= m; i ++)
{
b[i] = X[i-1] + 1;
c[i] = V[i-1];
//cin >> b[i] >> c[i];
kq.pb(c[i]);
}
sort(kq.begin(), kq.end());
kq.erase(unique(kq.begin(), kq.end()), kq.end());
sz = kq.size();
for(int i = 1; i <= n; i ++)
{
a[i] = lwr(a[i]);
add(a[i], 1);
val[a[i]].insert(i);
}
for(int i = 1; i <= m; i ++)c[i] = lwr(c[i]);
for(int i = 1; i <= n; i ++)
{
k = (*val[a[i]].rbegin()) - get(a[i]);
update(1, 1, sz, a[i], a[i], k);
}
vector<ll> res;
for(int i = 1; i <= m; i ++)
{
val[a[b[i]]].erase(b[i]);
val[c[i]].insert(b[i]);
add(a[b[i]], -1);
add(c[i], 1);
update(1, 1, n, a[b[i]]+1, sz, 1);
update(1, 1, n, c[i]+1, sz, -1);
cal(a[b[i]]);
cal(c[i]);
a[b[i]] = c[i];
//cout << st[1] << '\n';
res.pb(st[1]);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
70756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
70756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
72664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
70756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
