#include <bits/stdc++.h>
#include "bubblesort2.h"
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define pii pair <int,int>
#define s second
#define f first
#define pb push_back
using namespace std;
const int N = 1e6 + 5;
int l1[N],lz[4*N],AA[N],VV[N];
pii t[4*N];
map <int,int> mp;
void build(int h,int l,int r){
if (l == r){
t[h] = {0,l};
return;
}
build(left);
build(right);
t[h] = max(t[h*2],t[h*2 + 1]);
}
void push(int h){
if (lz[h]==0) return ;
lz[h*2] += lz[h];
lz[h*2 + 1] += lz[h];
t[h*2].f += lz[h];
t[h*2 + 1].f += lz[h];
lz[h] = 0;
}
void upd(int h,int l,int r,int L,int R,int val){
if (r < L || R < l) return;
if (L <= l && r <= R){
t[h].f += val;
lz[h] += val;
return;
}
push(h);
upd(left,L,R,val);
upd(right,L,R,val);
t[h] = max(t[h*2],t[h*2 + 1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
vector <pair <pii,int> > vec;
for (int i=0;i<A.size();i++){
vec.pb({{A[i],i},1});
}
for (int i=0;i<V.size();i++){
vec.pb({{V[i],i},2});
}
sort(vec.begin(),vec.end());
int m = vec.size();
for (int i = 0; i < vec.size(); i++){
int tp = vec[i].s;
if (tp == 1) AA[vec[i].f.s] = i + 1;
else VV[vec[i].f.s] = i + 1;
if (!i || vec[i].f.f != vec[i - 1].f.f)
l1[vec[i].f.f] = i + 1;
}
build(1,1,m);
for (int i = 0; i < A.size(); i++){
A[i] = AA[i];
upd(1,1,m,A[i],m,-1);
upd(1,1,m,A[i],A[i],i+1);
}
int Q=X.size();
vector<int> answer(Q);
for (int j = 0; j < X.size(); j++){
int i = X[j];
upd(1,1,m,A[i],m,+1);
upd(1,1,m,A[i],A[i],-i-1);
A[i] = VV[j];
upd(1,1,m,A[i],m,-1);
upd(1,1,m,A[i],A[i],i+1);
answer[j] = t[1].f;
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i=0;i<A.size();i++){
| ~^~~~~~~~~
bubblesort2.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i=0;i<V.size();i++){
| ~^~~~~~~~~
bubblesort2.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
bubblesort2.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < A.size(); i++){
| ~~^~~~~~~~~~
bubblesort2.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j = 0; j < X.size(); j++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3928 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
6104 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
