#include "bubblesort2.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int lmao = 4001000;
int qwq = 1000003;
struct node {
long long upd = 0, val = 0;
} st[lmao];
void u(int l, int r, int constl, int constr, int idx, long long val) {
if(l <= constl && constr <= r) {
st[idx].upd += val;
st[idx].val += val;
return;
}
int mid = (constl + constr) >> 1;
st[2*idx+1].upd += st[idx].upd;
st[2*idx+2].upd += st[idx].upd;
st[2*idx+1].val += st[idx].upd;
st[2*idx+2].val += st[idx].upd;
st[idx].upd = 0;
if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
else {
u(l, r, constl, mid, 2*idx + 1, val);
u(l, r, mid+1, constr, 2*idx + 2, val);
}
st[idx].val = max(st[2*idx+1].val, st[2*idx+2].val);
}
long long qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return st[idx].val;
int mid = (constl + constr) >> 1;
st[2*idx+1].upd += st[idx].upd;
st[2*idx+2].upd += st[idx].upd;
st[2*idx+1].val += st[idx].upd;
st[2*idx+2].val += st[idx].upd;
st[idx].upd = 0;
if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
else {
return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
}
void range_add(int l, int r, long long v) {
u(l, r, 0, qwq, 0, v);
}
long long query_max(int l, int r) {
return qu(l, r, 0, qwq, 0);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
ordered_set ost;
int N=A.size();
int Q=X.size();
std::vector<int> answer(Q);
set<int> s;
for(int i=0; i<N; i++) {
s.insert(A[i]);
}
for(int i=0; i<Q; i++) s.insert(V[i]);
unordered_map<int, int> is;
int nxt = 0;
for(int x: s) {
is[x] = nxt++;
}
for(int i=0; i<N; i++) A[i] = is[A[i]];
for(int i=0; i<Q; i++) V[i] = is[V[i]];
for(int i=0; i<N; i++) ost.insert({A[i], i});
pair<int, int> B[N];
for(int i=0; i<N; i++) {
B[i] = {A[i], i};
}
sort(B, B+N);
multiset<pair<int, int> > ms[N+Q];
unordered_map<int, int> ono[N+Q];
for(int i=0; i<N; i++) {
ms[B[i].first].insert({B[i].second - i, B[i].second});
ono[B[i].first][B[i].second] = B[i].second - i;
}
for(int i=0; i<N+Q; i++) {
if(ms[i].empty()) {
range_add(i, i, -1e17);
}
else {
range_add(i, i, (*ms[i].rbegin()).first);
}
}
for(int i=0; i<Q; i++) {
int x = A[X[i]];
int y = V[i];
if(A[X[i]] == V[i]) {
answer[i] = query_max(0, N+Q - 1);
continue;
}
if(x > y) swap(x, y);
if(x + 1 < y) {
if(A[X[i]] > V[i]) {
range_add(x+1, y-1, -1);
}
else {
range_add(x+1, y-1, 1);
}
}
x = A[X[i]];
y = V[i];
ms[x].erase({ono[x][X[i]], X[i]});
if(ms[x].size()) {
long long ogname = query_max(x, x);
long long q = (*ms[x].rbegin()).second;
ost.erase({x, X[i]});
ost.insert({y, X[i]});
range_add(x, x, q - (int)ost.order_of_key({A[q], q}) - ogname);
//cout << "tar " << q - (int)ost.order_of_key({A[q], q}) << "\n";
ost.erase({y, X[i]});
}
else {
ost.erase({x, X[i]});
long long ogname = query_max(x, x);
range_add(x, x, -1e17 - ogname); // res = -1e17
}
ost.insert({y, X[i]});
A[X[i]] = V[i];
ms[y].insert({X[i] - (int)ost.order_of_key({V[i], X[i]}), X[i]});
//cout << X[i] << " " << (int)ost.order_of_key({V[i], X[i]}) << " " << X[i] - (int)ost.order_of_key({V[i], X[i]}) << " g\n";
long long q = (*ms[y].rbegin()).second;
long long ogname = query_max(V[i], V[i]);
range_add(V[i], V[i], q - (int)ost.order_of_key({A[q], q}) - ogname);
answer[i] = query_max(0, N + Q - 1);
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
9176 KB |
Output is correct |
| 2 |
Correct |
178 ms |
16968 KB |
Output is correct |
| 3 |
Incorrect |
299 ms |
25400 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
