#include "bubblesort2.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct SEG{
SEG(int l, int r, int mx, int lazy, int sum) : l(l), r(r), mx(mx), lazy(lazy), sum(sum) {}
int l, r;
int mx, lazy;
int sum;
};
vector<SEG> seg;
void init(int idx, int s, int e){
if(s==e) return;
seg[idx].l = seg.size(); seg.pb({-1, -1, -INF, 0, 0});
seg[idx].r = seg.size(); seg.pb({-1, -1, -INF, 0, 0});
init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
}
void update(int idx, int s, int e, int x, int y){
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(y==-INF){
seg[idx].sum--;
}else{
seg[idx].sum++;
}
if(s==e){
seg[idx].mx = y;
return;
}
if(x<=(s+e)/2){
update(seg[idx].l, s, (s+e)/2, x, y);
}else{
update(seg[idx].r, (s+e)/2+1, e, x, y);
}
seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}
void lazy(int idx, int s, int e, int x, int y, int z){
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(x<=s && e<=y){
seg[idx].lazy += z;
seg[idx].mx += z;
return;
}
if(x>e || y<s) return;
lazy(seg[idx].l, s, (s+e)/2, x, y, z);
lazy(seg[idx].r, (s+e)/2+1, e, x, y, z);
seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}
int max(int idx, int s, int e, int x, int y){
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(x<=s && e<=y){
return seg[idx].mx;
}
if(s>y || e<x) return -INF;
return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}
int sum(int idx, int s, int e, int x, int y){
if(x<=s && e<=y){
return seg[idx].sum;
}else if(x>e || y<s) return 0;
return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}
vector<pii> vt;
map<pii, int> mp;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int Q = X.size();
vector<int> answer(Q);
for(int i=0; i<A.size(); i++){
vt.pb({A[i], i});
}
for(int i=0; i<Q; i++){
vt.pb({V[i], X[i]});
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());
for(int i=0; i<vt.size(); i++){
mp[vt[i]] = i;
}
seg.pb({-1, -1, -INF, 0, 0});
init(0, 0, vt.size()-1);
for(int i=0; i<A.size(); i++){
int t = mp[{A[i], i}];
update(0, 0, vt.size()-1, t, i);
}
for(int i=0; i<A.size(); i++){
int t = mp[{A[i], i}];
lazy(0, 0, vt.size()-1, t+1, vt.size()-1, -1);
}
for(int i=0; i<Q; i++){
int idx = X[i];
pii prv = {A[idx], idx};
update(0, 0, vt.size()-1, mp[prv], -INF);
lazy(0, 0, vt.size()-1, mp[prv]+1, vt.size()-1, 1);
pii now = {V[idx], idx};
A[idx] = V[idx];
update(0, 0, vt.size()-1, mp[now], idx - sum(0, 0, vt.size()-1, 0, mp[now]-1));
lazy(0, 0, vt.size()-1, mp[now]+1, vt.size()-1, -1);
answer[i] = max(0, 0, vt.size()-1, 0, vt.size()-1);
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<A.size(); i++){
~^~~~~~~~~
bubblesort2.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<vt.size(); i++){
~^~~~~~~~~~
bubblesort2.cpp:127:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<A.size(); i++){
~^~~~~~~~~
bubblesort2.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<A.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
4056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
