#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]);
ost.insert({A[i], 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]];
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[2*N];
unordered_map<int, int> ono[2*N];
for(int i=0; i<N; i++) {
ms[B[i].first].insert({B[i].second - i, B[i].second});
//cout << "ms[" << B[i].first << "] insert {" << B[i].second - i << ", " << B[i].second << "}\n";
ono[B[i].first][B[i].second] = B[i].second - i;
}
for(int i=0; i<2*N; 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, 2*N - 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);
}
}
ms[A[X[i]]].erase({ono[A[X[i]]][X[i]], X[i]});
if(ms[A[X[i]]].empty()) {
long long ogname = query_max(A[X[i]], A[X[i]]);
range_add(A[X[i]], A[X[i]], -1e17 - ogname);
}
else {
long long ogname = query_max(A[X[i]], A[X[i]]);
range_add(A[X[i]], A[X[i]], (*ms[A[X[i]]].rbegin()).first - ogname);
}
ost.erase({A[X[i]], X[i]});
A[X[i]] = V[i];
ost.insert({A[X[i]], X[i]});
ms[A[X[i]]].insert({X[i] - ost.order_of_key({A[X[i]], X[i]}), X[i]});
ono[A[X[i]]][X[i]] = X[i] - ost.order_of_key({A[X[i]], X[i]});
long long ogname = query_max(A[X[i]], A[X[i]]);
//cout << "ogname " << ogname <<"\n";
range_add(A[X[i]], A[X[i]], (*ms[A[X[i]]].rbegin()).first - ogname);
answer[i] = query_max(0, 2*N - 1);
//cout << "mengbier updates = " << (*ms[A[X[i]]].rbegin()).first << "\n";
//cout << "Answer = " << query_max(0, 2*N - 1) << '\n';
//for(int i=0; i<2*N; i++) cout << (query_max(i, i) == -1e17 ? -1 : query_max(i, i)) << ' ';
//cout << '\n';
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
12644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
