#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int lz, mx, l, r;
};
const int MAXN=5e5+5;
const int MAIOR=1e9+7;
int v[MAXN];
vector<node> seg;
int n, q;
int novo() {
node cur;
cur.lz=cur.mx=cur.l=cur.r=0;
seg.push_back(cur);
return seg.size()-1;
}
void refresh(int sind, int ini, int fim) {
seg[sind].mx+=seg[sind].lz;
// printf("modifica mx[%d; %d] >> %d\n", ini, fim, seg[sind].mx);
if(ini==fim) {
seg[sind].lz=0;
return;
}
if(!seg[sind].l) { int aux=novo(); seg[sind].l=aux; }
if(!seg[sind].r) { int aux=novo(); seg[sind].r=aux; }
seg[seg[sind].l].lz+=seg[sind].lz;
seg[seg[sind].r].lz+=seg[sind].lz;
seg[sind].lz=0;
}
void update(int sind, int ini, int fim, int qini, int qfim, int val) {
refresh(sind, ini, fim);
if(qini>fim||qfim<ini) return;
if(qini<=ini&&qfim>=fim) {
seg[sind].lz+=val;
refresh(sind, ini, fim);
return;
}
int e=seg[sind].l; int d=seg[sind].r;
int m=(ini+fim)/2;
update(e, ini, m, qini, qfim, val);
update(d, m+1, fim, qini, qfim, val);
seg[sind].mx=max(seg[e].mx, seg[d].mx);
}
void query(int sind, int ini, int fim) {
refresh(sind, ini, fim);
if(ini==fim) {
printf("%d [%d]: %d %d\n", sind, ini, seg[sind].mx, seg[sind].lz);
return;
}
int e=seg[sind].l; int d=seg[sind].r;
int m=(ini+fim)/2;
query(e, ini, m); query(d, m+1, fim);
}
vector<int> countScans(vector<int> A, vector<int> qi, vector<int> qv){
vector<int> respf;
n=A.size(); q=qi.size();
novo(); novo();
for(int i=0; i<n; i++) {
v[i]=A[i];
update(1, 1, MAIOR, v[i]+1, MAIOR, -1);
update(1, 1, MAIOR, v[i], v[i], i);
}
// query(1, 1, MAIOR);
for(int i=0; i<q; i++) {
int ind=qi[i]; int val=qv[i];
// printf("query %d %d\n", ind, val);
update(1, 1, MAIOR, v[ind]+1, MAIOR, 1);
update(1, 1, MAIOR, v[ind], v[ind], ind);
// query(1, 1, MAIOR);
v[ind]=val;
update(1, 1, MAIOR, v[ind]+1, MAIOR, -1);
update(1, 1, MAIOR, v[ind], v[ind], ind);
int resp=seg[1].mx;
respf.push_back(resp);
// printf("ok %d\n", resp);
}
return respf;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
