#include "bubblesort2.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e6 + 7;
struct node {
int mx, add, lz;
node(int x = 0) {
mx = x;
add = lz = 0;
}
} t[N * 4];
int n;
void apply(int v, int x) {
t[v].mx += x;
t[v].add += x;
t[v].lz += x;
}
void push(int v) {
apply(v * 2, t[v].lz);
apply(v * 2 + 1, t[v].lz);
t[v].lz = 0;
}
void pull(int v) {
t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}
void build(int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1) {
t[v] = node(-INF);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
pull(v);
}
void add(int l, int r, int x, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
apply(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
pull(v);
}
void set_val(int pos, int x, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1) {
t[v] = node(x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(pos < tm) set_val(pos, x, v * 2, tl, tm);
else set_val(pos, x, v * 2 + 1, tm, tr);
pull(v);
}
int get_add(int pos, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1)
return t[v].add;
push(v);
int tm = (tl + tr) / 2;
if(pos < tm) return get_add(pos, v * 2, tl, tm);
else return get_add(pos, v * 2 + 1, tm, tr);
}
vi countScans(vi A, vi X, vi Y) {
int Q = X.size(), N = A.size();
V<pi> v;
for(int i = 0; i < N; i++) v.EB(A[i], i);
for(int i = 0; i < Q; i++) v.EB(Y[i], X[i]);
map<pi, int> id;
sort(ALL(v));
v.resize(unique(ALL(v)) - v.begin());
for(int i = 0; i < v.size(); i++)
id[v[i]] = i;
n = v.size();
build();
for(int i = 0; i < N; i++) {
int x = id[{A[i], i}];
A[i] = x;
set_val(x, i);
}
for(int i = 0; i < N; i++)
if(A[i] + 1 < n)
add(A[i] + 1, n, -1);
vi ans(Q);
for(int i = 0; i < Q; i++) {
int pos = X[i], val = Y[i], old_val = A[pos];
val = id[{val, pos}];
// old_val -> val
if(old_val + 1 < n)
add(old_val + 1, n, 1);
set_val(old_val, -INF);
int added = get_add(val);
set_val(val, added + pos);
if(val + 1 < n)
add(val + 1, n, -1);
ans[i] = t[1].mx;
}
return ans;
}
Compilation message
bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
49764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
