#include "bubblesort2.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define inf (int)(1e17+1)
#define mod (int)(1e9+7)
#define N (int)(5e5+5)
#define fi first
#define se second
#define endl "\n"
#define eps (double)(1e-9)
#define sa cout<<"sa"<<endl
using namespace std;
struct segtree{
int n;
vector <vector<int>> seg;
segtree(int n) : n(n), seg(4*n){};
void update(int x,int a,int j,int l,int r){
if(l==r) {seg[j].clear();seg[j].push_back(x);return;}
int m=(l+r)>>1;
if(a<=m) update(x,a,2*j,l,m);
else update(x,a,2*j+1,m+1,r);
seg[j].clear();
int cura=0,curb=0;
while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
if(seg[2*j][cura]<seg[2*j+1][curb])
seg[j].push_back(seg[2*j][cura++]);
else seg[j].push_back(seg[2*j+1][curb++]);
}
while(cura!=seg[2*j].size()) seg[j].push_back(seg[2*j][cura++]);
while(curb!=seg[2*j+1].size()) seg[j].push_back(seg[2*j+1][curb++]);
}
int query(int x,int a,int b,int j,int l,int r){
if(a>r||b<l) return 0;
if(a<=l&&r<=b) return lower_bound(all(seg[j]),x)-seg[j].begin();
int m=(l+r)>>1;
return query(x,a,b,2*j,l,m)+query(x,a,b,2*j+1,m+1,r);
}
int query(int x,int l,int r) {return query(x,l,r,1,0,n-1);}
void update(int x,int i) {update(x,i,1,0,n-1);}
};
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
int n=a.size();
int q=x.size();
vector<int> ans(q);
segtree seg1(n),seg2(n);
int cur=0;
for(int i=0;i<n;i++) {
seg1.update(a[i],i);
seg2.update(-a[i],i);
}
for(int i=0;i<n;i++) cur+=seg1.query(a[i],i,n-1);
for(int i=0;i<q;i++){
int id=x[i];
cur-=seg1.query(a[id],id,n-1)+seg2.query(-a[id],0,id);
seg1.update(v[i],id);
seg2.update(-v[i],id);
cur+=seg1.query(a[id],id,n-1)+seg2.query(-a[id],0,id);
ans[i]=cur;
}
return ans;
}
Compilation message
bubblesort2.cpp: In member function 'void segtree::update(int, int, int, int, int)':
bubblesort2.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
| ~~~~^~~~~~~~~~~~~~~~~
bubblesort2.cpp:27:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
| ~~~~^~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while(cura!=seg[2*j].size()) seg[j].push_back(seg[2*j][cura++]);
| ~~~~^~~~~~~~~~~~~~~~~
bubblesort2.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(curb!=seg[2*j+1].size()) seg[j].push_back(seg[2*j+1][curb++]);
| ~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6755 ms |
12156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
