#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int mx, qtd, lz;
};
const int MAXN = 5e5+5;
const int INF = 5e7;
map<int, int> mp;
vector<int> ans;
int pos[MAXN];
int mpcnt[MAXN], mpaux[MAXN];
node seg[MAXN*4];
int n, q, mpn;
void refresh(int sind, int l, int r) {
if(!seg[sind].lz) return;
seg[sind].mx += seg[sind].lz;
int val = seg[sind].lz;
seg[sind].lz = 0;
if(l == r) return;
int e = sind*2; int d = e+1;
seg[e].lz += val;
seg[d].lz += val;
}
int query(int sind, int l, int r, int ql, int qr) {
refresh(sind, l, r);
if(ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return seg[sind].qtd;
int m = (l+r)/2;
int e = sind*2; int d = e+1;
return query(e, l, m, ql, qr) + query(d, m+1, r, ql, qr);
}
void update1(int sind, int l, int r, int qind, int val) {
refresh(sind, l, r);
if(qind > r || qind < l) return;
if(l == r) {
seg[sind].mx = val;
seg[sind].qtd = val>=0;
return;
}
int m = (l+r)/2;
int e = sind*2; int d = e+1;
update1(e, l, m, qind, val);
update1(d, m+1, r, qind, val);
seg[sind].mx = max(seg[e].mx, seg[d].mx);
seg[sind].qtd = seg[e].qtd + seg[d].qtd;
}
void update2(int sind, int l, int r, int ql, int qr, int val) {
refresh(sind, l, r);
if(ql > r || qr < l) return;
if(ql <= l && qr >= r) {
seg[sind].lz += val;
refresh(sind, l, r);
return;
}
int m = (l+r)/2;
int e = sind*2; int d = e+1;
update2(e, l, m, ql, qr, val);
update2(d, m+1, r, ql, qr, val);
seg[sind].mx = max(seg[e].mx, seg[d].mx);
seg[sind].qtd = seg[e].qtd + seg[d].qtd;
}
vector<int> countScans(vector<int> input, vector<int> qi, vector<int> qv){
n = input.size();
q = qi.size();
for(int val : input) mp[val] = 1;
for(int val : qv) mp[val] = 1;
for(auto &mit : mp) mit.second = ++mpn;
for(int &val : input) val = mp[val], mpcnt[val]++;
for(int &val : qv) val = mp[val], mpcnt[val]++;
for(int i = 2; i <= mpn; i++) mpcnt[i] += mpcnt[i-1];
mpn = mpcnt[mpn];
for(int i = 1; i <= 4*mpn; i++) seg[i].mx = -INF;
for(int i = 0; i < n; i++) {
int val = input[i];
mpaux[val]++;
pos[i] = mpcnt[val-1]+mpaux[val];
int presum = query(1, 1, mpn, 1, mpcnt[val]);
update2(1, 1, mpn, mpcnt[val-1]+1, mpn, -1);
update1(1, 1, mpn, pos[i], i-presum);
}
// printf("mx %d\n", seg[1].mx);
for(int i = 0; i < q; i++) {
int ind = qi[i], val = qv[i];
update1(1, 1, mpn, pos[ind], -INF);
update2(1, 1, mpn, mpcnt[input[ind]]+1, mpn, 1);
input[ind] = val;
mpaux[val]++;
pos[ind] = mpcnt[val-1]+mpaux[val];
int presum = query(1, 1, mpn, 1, mpcnt[val]);
// printf("%d: %d - %d %d >> %d\n", ind, val, pos[ind], presum, ind-presum);
update2(1, 1, mpn, mpcnt[val-1]+1, mpn, -1);
update1(1, 1, mpn, pos[ind], ind-presum);
ans.push_back(seg[1].mx);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
