#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 500'032;
const int Sa = 4096, Sq = 4096;
int cnt_gt[N];
int val[N];
short cnt_gt_arange[Sa];
short val_arange[Sa];
int mx_qrange[Sq];
int added_to[N];
vector<int> ans;
int n, q, qx[N], qy[N];
int fen[N];
void fen_add(int i, int x)
{
++i;
while (i < N) {
fen[i] += x;
i += i & -i;
}
}
int fen_get(int r)
{
int ans = 0;
while (r > 0) {
ans += fen[r];
r -= r & -r;
}
return ans;
}
int mx_init;
void init()
{
vector<int> cmp(val, val+n);
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
int mx = cmp.size() - 1;
mx_init = 0;
Loop (i,0,n) {
int j = lower_bound(cmp.begin(), cmp.end(), val[i])
- cmp.begin();
cnt_gt[i] = fen_get(mx-j);
mx_init = max(mx_init, cnt_gt[i]);
fen_add(mx-j, 1);
}
}
#define OPTIM __attribute__((optimize("O3,unroll-loops"),target("avx2")))
OPTIM pair<short,short> do_cnt_gt(int l, int r, short x)
{
short ans = 0;
short mx = -32768;
Loop (i,l,r) {
ans += val_arange[i] > x;
mx = cnt_gt_arange[i] > mx? cnt_gt_arange[i]: mx;
}
return {ans, mx};
}
OPTIM short do_sub_inrange(int l, int r, short xl, short xr)
{
short mx = -32768;
Loop (i,l,r) {
short cnt = cnt_gt_arange[i];
short val = val_arange[i];
cnt -= xl <= val && val < xr;
mx = cnt > mx? cnt: mx;
cnt_gt_arange[i] = cnt;
}
return mx;
}
OPTIM short do_add_inrange(int l, int r, short xl, short xr)
{
short mx = -32768;
Loop (i,l,r) {
short cnt = cnt_gt_arange[i];
short val = val_arange[i];
cnt += xl <= val && val < xr;
mx = cnt > mx? cnt: mx;
cnt_gt_arange[i] = cnt;
}
return mx;
}
short apply(int al, int ar, int qi, int mx_cnt, const vector<int> &cmp)
{
int i = qx[qi], x = qy[qi];
short y = lower_bound(cmp.begin(), cmp.end(), x)
- cmp.begin();
short mx = -32768;
if (al < i) {
int cr = min(ar, i);
auto [tmp, new_mx] = do_cnt_gt(0, cr-al, y);
added_to[qi] += tmp;
mx = max(mx, new_mx);
}
if (i+1 < ar) {
int cl = max(al, i+1);
if (val[i] < x) {
short yl = lower_bound(cmp.begin(), cmp.end(),
val[i]) - cmp.begin();
auto tmp = do_add_inrange(cl-al, ar-al, yl, y);
mx = max(mx, tmp);
} else {
short yr = lower_bound(cmp.begin(), cmp.end(),
val[i]) - cmp.begin();
auto tmp = do_sub_inrange(cl-al, ar-al, y, yr);
mx = max(mx, tmp);
}
}
if (al <= i && i < ar) {
val[i] = x;
val_arange[i-al] = y;
cnt_gt[i] = added_to[qi];
if (cnt_gt[i] - mx_cnt < -16384)
cnt_gt_arange[i-al] = -16384;
else
cnt_gt_arange[i-al] = cnt_gt[i] - mx_cnt;
mx = max(mx, cnt_gt_arange[i-al]);
}
return mx;
}
void solve_arange(int ql, int qr, int al, int ar)
{
int mx_cnt = ans.size()? ans.back(): mx_init;
Loop (i,al,ar) {
if (cnt_gt[i] - mx_cnt < -16384)
cnt_gt_arange[i-al] = -16384;
else
cnt_gt_arange[i-al] = cnt_gt[i] - mx_cnt;
}
vector<int> cmp;
Loop (i,al,ar)
cmp.push_back(val[i]);
Loop (i,ql,qr)
cmp.push_back(qy[i]);
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
Loop (i,al,ar)
val_arange[i-al] = lower_bound(cmp.begin(), cmp.end(),
val[i]) - cmp.begin();
Loop (i,ql,qr) {
int x = apply(al, ar, i, mx_cnt, cmp);
x += mx_cnt;
mx_qrange[i-ql] = max(mx_qrange[i-ql], x);
}
Loop (i,al,ar) {
if (cnt_gt[i] - mx_cnt < -16384)
cnt_gt[i] += (int)cnt_gt_arange[i-al] + 16384;
else
cnt_gt[i] = (int)cnt_gt_arange[i-al] + mx_cnt;
}
}
void solve_qrange(int ql, int qr)
{
vector<int> ch;
Loop (i,ql,qr)
ch.push_back(val[qx[i]]);
memset(mx_qrange, 0, sizeof(mx_qrange));
for (int al = 0; al < n; al += Sa) {
int ar = min(al + Sa, n);
solve_arange(ql, qr, al, ar);
Loop (i,ql,qr)
val[qx[i]] = ch[i-ql];
}
Loop (i,ql,qr)
val[qx[i]] = qy[i];
Loop (i,ql,qr)
ans.push_back(mx_qrange[i-ql]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
n = A.size();
Loop (i,0,n)
val[i] = A[i];
q = X.size();
Loop (i,0,q) {
qx[i] = X[i];
qy[i] = V[i];
}
for (int ql = 0; ql < q; ql += Sq) {
int qr = min(ql+Sq, q);
solve_qrange(ql, qr);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
