#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6 + 100;
vector<int> a, pos, val, ans;
int timer;
map<int, int> mp;
set<int> ind[mxn];
int tree[4 * mxn], lazy[4 * mxn], lz[4 * mxn];
void push(int v, int l, int r) {
if (r < l) return;
if (lz[v] != 0) {
tree[v] += lazy[v];
if (l != r) {
lz[2 * v] = 1;
lz[2 * v + 1] = 1;
tree[2 * v] += lazy[v];
tree[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
lz[v] = 0;
}
}
void update(int v, int tl, int tr, int ql, int qr, int val) {
push(v, tl, tr);
if (tl > tr || tl > qr || tr < ql) return;
if (tl >= ql && tr <= qr) {
lz[v] = 1;
lazy[v] += val;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, ql, qr, val);
update(2 * v + 1, tm + 1, tr, ql, qr, val);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
void rem(int v, int x) {
update(0, 0, timer - 1, x, timer - 1, 1);
if (v == *ind[v].rbegin()) {
auto it = ind[v].rbegin();
int val = -*it;
it--;
val += *it;
update(0, 0, timer - 1, x, x, val);
}
ind[x].erase(v);
}
void add(int v, int x) {
update(0, 0, timer - 1, x, timer - 1, -1);
if (v > *ind[x].rbegin()) {
update(0, 0, timer - 1, x, x, v - *ind[x].rbegin());
}
ind[x].insert(v);
a[v] = x;
}
void solve() {
for (auto it : a) mp[it] = 1;
for (auto it : val) mp[it] = 1;
for (auto &it : mp) {
it.second = timer++;
}
for (int i = 0; i < timer; i++) {
ind[i].insert(-mxn);
}
for (int i = 0; i < a.size(); i++) {
a[i] = mp[a[i]];
ind[a[i]].insert(i);
update(0, 0, timer - 1, a[i], timer - 1, -1);
}
for (int i = 0; i < timer; i++) {
update(0, 0, timer - 1, i, i, *ind[i].rbegin());
}
for (int q = 0; q < pos.size(); q++) {
rem(pos[q], a[pos[q]]);
add(pos[q], mp[val[q]]);
ans.push_back(tree[0] + 1);
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
a = A;
pos = X;
val = V;
solve();
return ans;
}
Compilation message
bubblesort2.cpp: In function 'void solve()':
bubblesort2.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
bubblesort2.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int q = 0; q < pos.size(); q++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
98976 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
