#include <bits/stdc++.h>
#include "bubblesort2.h"
#include <ext/pb_ds/assoc_container.hpp>
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 1e4+5;
const int MAX_VAL = 1e6;
double PI=3.14159265359;
int arx[8]={1,1,0,-1,-1,-1, 0, 1};
int ary[8]={0,1,1, 1, 0,-1,-1,-1};
/*typedef complex<int> Point;
#define X real()
#define Y imag()*/
/*void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}*/
vector<pair<ll,int>> tab(nax);
vi segtree(nax*4);
vi upd(nax*4);
void update(int left,int right,int value,int pos,int l,int r)
{
if (l>=left&&r<=right){
upd[pos]+=value;
segtree[pos]+=value;
return;
}
if (r<=left||l>=right) return;
int mid=(l+r)/2;
update(left,right,value,pos*2+1,l,mid);
update(left,right,value,pos*2+2,mid,r);
segtree[pos] = max(segtree[pos*2+1],segtree[pos*2+2])+upd[pos];
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
int n,q;
n=A.size();
q=X.size();
vi nabba;
vi check(n+q);
map<int,int> ind;
for (int i = 0; i < n; ++i)
{
check[i]=A[i];
}
for (int i = 0; i < q; ++i)
{
check[i+n]=V[i];
}
sort(check.begin(),check.end());
int cur=0;
for (int i = 0; i < check.size(); ++i)
{
if (i==0) {
ind[check[i]]=cur;
cur++;
}
else{
if (check[i]==check[i-1]) {
cur++;
continue;
}
ind[check[i]]=cur;
cur++;
}
}
map<int,set<int>> pos;
for (int i = 0; i < n; ++i)
{
pos[ind[A[i]]].insert(i);
//cout << ind[A[i]]<<endl;
update(ind[A[i]],cur,-1,0,0,cur+1);
}
for (int i = 0; i < cur; ++i)
{
if ((int)pos[i].size()>0){
update(i,i+1,*pos[i].rbegin()+1,0,0,cur+1);
}
}
for (int i = 0; i < q; ++i)
{
int x=X[i];
int nw=V[i];
int lst=A[i];
A[x]=nw;
lst=ind[lst];
nw=ind[nw];
int lstpos=*pos[lst].rbegin();
pos[lst].erase(x);
if ((int)pos[lst].size()>0) update(lst,lst+1,(*pos[lst].rbegin()-lstpos),0,0,cur+1);
else update(lst,lst+1,-lstpos-1,0,0,cur+1);
update(lst,cur,1,0,0,cur+1);
if ((int)pos[nw].size()==0){
pos[nw].insert(x);
update(nw,nw+1,x+1,0,0,cur+1);
}else{
lstpos=*pos[nw].rbegin();
pos[nw].insert(x);
update(nw,nw+1,(*pos[nw].rbegin()-lstpos),0,0,cur+1);
}
update(nw,cur,-1,0,0,cur+1);
nabba.pb(segtree[0]);
//cout << segtree[0]<<endl;
}
return nabba;
}
/*int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}*/
/*int main(){
optimise;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
//setIO("cowland");
}*/
/*int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int N,Q;
N=readInt();
Q=readInt();
std::vector<int> A(N);
for(int i=0;i<N;i++)
A[i]=readInt();
std::vector<int> X(Q),V(Q);
for(int j=0;j<Q;j++){
X[j]=readInt();
V[j]=readInt();
}
std::vector<int> res=countScans(A,X,V);
for(int j=0;j<int(res.size());j++)
printf("%d\n",res[j]);
}*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < check.size(); ++i)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
5416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
