#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 500050
int n, q, tr[4*maxn], a[maxn];
set<pair<int,int>> lr;
void att(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
else if(l == r) {
tr[no]+= val;
return;
}
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
att(f1,l,mid,pos,val);
att(f2,mid+1,r,pos,val);
tr[no] = tr[f1]+tr[f2];
}
//busca na seg para encontrar o k-ésimo menor
int find(int no, int l, int r, int val) {
if(l == r) {
return l;
}
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
if(val-tr[f1] > 0) {
return find(f2,mid+1,r,val-tr[f1]);
}
else {
return find(f1,l,mid,val);
}
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
vector<int> answer;
vector<int> cc;
n = A.size();
q = V.size();
for(int i = 1; i <= n; i++) {
a[i] = A[i-1];
cc.pb(a[i]);
}
for(int i = 0; i < q; i++) {
cc.pb(V[i]);
}
sort(all(cc));
cc.erase(unique(all(cc)),cc.end());
int mxv = cc.size();
for(int i = 1; i <= n; i++) {
a[i] = upper_bound(all(cc),a[i]) - cc.begin();
att(1,1,mxv,a[i],1);
}
for(int i = 0; i < q; i++) {
V[i] = upper_bound(all(cc),V[i]) - cc.begin();
}
//mantem os intervalos crescentes
int ant = 1;
for(int i = 2; i <= n; i++) {
if(a[i] < a[i-1]) {
lr.insert(mp(ant,i-1));
ant = i;
}
}
lr.insert(mp(ant,n));
for(int i = 0; i < q; i++) {
int pos = X[i]+1;
int val = V[i];
//muda a seg
att(1,1,mxv,a[pos],-1);
att(1,1,mxv,val,1);
auto it = lr.upper_bound(mp(pos,inf1)); it--;
int l1 = it->fr;
int r1 = it->sc;
if((pos+1 <= r1 && val > a[pos+1]) || (pos-1 >= l1 && val < a[pos-1])) {
lr.erase(it);
if(pos-1 >= l1) lr.insert(mp(l1,pos-1));
lr.insert(mp(pos,pos));
if(pos+1 <= r1) lr.insert(mp(pos+1,r1));
}
else if(l1 == pos && r1 == pos) {
vector<pair<int,int>> rem;
if(it != lr.begin()) {
auto itl = it; itl--;
if(val >= itl->sc) {
l1 = itl->fr;
rem.pb(mp(itl->fr,itl->sc));
}
}
auto itr = it; itr++;
if(itr != lr.end()) {
if(val <= itr->fr) {
r1 = itr->sc;
rem.pb(mp(itr->fr,itr->sc));
}
}
rem.pb(mp(it->fr,it->sc));
for(auto x : rem) lr.erase(x);
lr.insert(mp(l1,r1));
}
else if(l1 == pos) {
vector<pair<int,int>> rem;
if(it != lr.begin()) {
auto itl = it; itl--;
if(val >= itl->sc) {
l1 = itl->fr;
rem.pb(mp(itl->fr,itl->sc));
}
}
rem.pb(mp(it->fr,it->sc));
for(auto x : rem) lr.erase(x);
lr.insert(mp(l1,r1));
}
else if(r1 == pos) {
vector<pair<int,int>> rem;
auto itr = it; itr++;
if(itr != lr.end()) {
if(val <= itr->fr) {
r1 = itr->sc;
rem.pb(mp(itr->fr,itr->sc));
}
}
rem.pb(mp(it->fr,it->sc));
for(auto x : rem) lr.erase(x);
lr.insert(mp(l1,r1));
}
//separar em (l1,pos-1) (pos,pos) e (pos+1,r1)
//juntar com o anterior se for o inicio
//juntar com o proximo se for o final
a[pos] = val;
//faz bb para encontrar o ultimo no primeiro intervalo que funciona
l1 = 1;
r1 = lr.begin()->sc;
int ans1 = 0;
while(l1 <= r1) {
int mid = (l1+r1)>>1;
//vê se o mid ésimo menor é igual ao a[mid]
if(a[mid] == find(1,1,mxv,mid)) {
ans1 = mid;
l1 = mid+1;
}
else {
r1 = mid-1;
}
}
it = lr.end(); it--;
int l2 = it->fr;
int r2 = n;
int ans2 = n+1;
while(l2 <= r2) {
int mid = (l2+r2)>>1;
//vê se o mid ésimo menor é igual ao a[mid]
if(a[mid] == find(1,1,mxv,mid)) {
ans2 = mid;
r2 = mid-1;
}
else {
l2 = mid+1;
}
}
answer.pb(max(ans2-ans1-1-1,0));
// cout << ans1 << " " << ans2 << endl;
}
return answer;
}
// int32_t main() {
// ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// // freopen("out.out", "w", stdout);
// int N, Q;
// cin >> N >> Q;
// vector<int> A,X,V;
// for(int i = 0; i < N; i++) {
// int x; cin >> x; A.pb(x);
// }
// for(int i = 0; i < Q; i++) {
// int x; cin >> x; X.pb(x);
// cin >> x; V.pb(x);
// }
// auto answer = countScans(A,X,V);
// for(auto x : answer) cout << x << endl;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
