#include<bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
using namespace std;
int offset[1000005],f[1000005],val[1000005],aint[4000005],lazy[4000005];
vector<int>aux;
int n,q,l;
void push(int nod,int st,int dr)
{
if (lazy[nod]){
aint[nod]+=lazy[nod];
if (st!=dr){
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
}
lazy[nod]=0;
}
}
void update(int nod,int st,int dr,int l,int r,int add)
{
if (l>r)
return ;
if (l<=st && dr<=r){
aint[nod]+=add;
if (st!=dr){
lazy[nod*2]+=add;
lazy[nod*2+1]+=add;
}
return ;
}
push(nod,st,dr);
int mij=(st+dr)/2;
if (l<=mij)
update(nod*2,st,mij,l,r,add);
if (mij+1<=r)
update(nod*2+1,mij+1,dr,l,r,add);
push(nod*2,st,mij);
push(nod*2+1,mij+1,dr);
aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
void update2(int nod,int st,int dr,int poz,int val)
{
if (st==dr){
aint[nod]+=val;
return ;
}
push(nod,st,dr);
int mij=(st+dr)/2;
if (poz<=mij)
update2(nod*2,st,mij,poz,val);
else
update2(nod*2+1,mij+1,dr,poz,val);
push(nod*2,st,mij);
push(nod*2+1,mij+1,dr);
aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
int add(int poz,int nr)
{
if (val[poz]!=2e9){
//update(1,0,l-1,val[poz]+1,l-1,1);
update2(1,0,l-1,val[poz],-poz);
}
val[poz]=nr;
//update(1,0,l-1,val[poz]+1,l-1,-1);
update2(1,0,l-1,val[poz],poz);
}
vector<int> countScans(vector<int>a,vector<int>x,vector<int>v)
{
n=a.size();
q=x.size();
int i;
for(i=0;i<n;i++)
aux.push_back(a[i]);
for(i=0;i<q;i++)
aux.push_back(v[i]);
sort(aux.begin(),aux.end());
aux.resize(unique(aux.begin(),aux.end())-aux.begin());
for(i=0;i<n;i++)
a[i]=lower_bound(aux.begin(),aux.end(),a[i])-aux.begin();
for(i=0;i<q;i++)
v[i]=lower_bound(aux.begin(),aux.end(),v[i])-aux.begin();
l=n+q;
for(i=0;i<n;i++)
offset[a[i]+1]++;
for(i=0;i<q;i++)
offset[v[i]+1]++;
for(i=2;i<aux.size();i++)
offset[i]=offset[i-1]+offset[i];
for(i=0;i<n;i++)
val[i]=2e9;
vector<int>ans;
for(i=0;i<n;i++)
add(i,offset[a[i]]+f[a[i]]),f[a[i]]++;
/*for(i=0;i<q;i++){
add(x[i],offset[v[i]]+f[v[i]]),f[v[i]]++;
ans.push_back(aint[1]);
}*/
return ans;
}
Compilation message
bubblesort2.cpp: In function 'int add(int, int)':
bubblesort2.cpp:66:1: warning: no return statement in function returning non-void [-Wreturn-type]
66 | }
| ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(i=2;i<aux.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1772 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
