#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define ll long long
const int base = 1<<20;
const ll INF = 1e18+7;
const ll MAXN = 1e6+7;
ll tree[base<<1];
set<int> pozycje[MAXN];
ll lazy[base<<1];
int n;
void build(ll v, ll l, ll r){
if(l == r){
if(l > n){
tree[v] = -INF;
return;
}
auto tmp = pozycje[l].end();
--tmp;
tree[v] = -(n - *tmp - 1);
}
else{
ll mid = (l + r)/2;
build(2*v, l, mid);
build(2*v+1, mid+1, r);
tree[v] = max(tree[2*v], tree[2*v+1]);
}
}
void push(ll v){
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
tree[2*v] += lazy[v];
tree[2*v+1] += lazy[v];
lazy[v] = 0;
}
ll p, k;
ll val;
void update(ll v, ll l, ll r){
if(l > k || r < p) return;
if(p <= l && r <= k){
tree[v] += val;
lazy[v] += val;
}
else{
ll mid = (l+r)/2;
push(v);
update(2*v, l, mid);
update(2*v+1, mid+1, r);
tree[v] = max(tree[2*v], tree[2*v+1]);
}
}
ll query(ll v, ll l, ll r){
if(l > k || r < p) return -INF;
if(p <= l && r <= k){
return tree[v];
}
else{
ll mid = (l+r)/2;
push(v);
auto lQ = query(2*v, l, mid);
auto rQ = query(2*v+1, mid+1, r);
return max(lQ, rQ);
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
int Q = X.size();
vector<int> res(Q);
map<long long, int> skalowanie;
for(auto i : A){
skalowanie[i] = 0;
}
for(auto i : V){
skalowanie[i] = 0;
}
int id = 0;
for(auto &i : skalowanie) i.second = ++id, pozycje[i.second].insert(-1);
for(ll i = 0; i < n; ++i){
auto vi = A[i];
pozycje[skalowanie[vi]].insert(i);
}
build(1, 1, id);
// for(int i = 0; i <= id; ++i){
// p = k = i;
// cerr << query(1, 1, n) << " ";
// }
// cerr << "\n";
for(int i = 0; i < n; ++i){
auto vi = A[i];
p = 0, k = skalowanie[vi]-1;
val = 1;
update(1, 1, id);
}
// for(int i = 0; i <= id; ++i){
// p = k = i;
// cerr << query(1, 1, n) << " ";
// }
// cerr << "\n";
for(int i = 0; i < Q; ++i){
p = 0, k = skalowanie[A[X[i]]]-1;
val = -1;
update(1, 1, id);
pozycje[skalowanie[A[X[i]]]].erase(X[i]);
auto tmp = pozycje[skalowanie[A[X[i]]]].end();
--tmp;
p = k = skalowanie[A[X[i]]];
val = max(*tmp, 0) - X[i];
if(*tmp == -1) val -= INF;
// cerr << A[X[i]] << " " << *tmp << ": " << val << "\n";
update(1, 1, id);
// for(int i = 0; i <= id; ++i){
// p = k = i;
// cerr << query(1, 1, n) << " ";
// }
// cerr << "\n";
A[X[i]] = V[i];
p = 0, k = skalowanie[A[X[i]]]-1;
val = 1;
update(1, 1, id);
tmp = pozycje[skalowanie[A[X[i]]]].end();
--tmp;
p = k = skalowanie[A[X[i]]];
if(X[i] > *tmp){
// cerr << V[i] << ": " << *tmp << "\n";
val = X[i] - max(*tmp, 0);
if(*tmp == -1) val += INF;
update(1, 1, id);
}
pozycje[skalowanie[A[X[i]]]].insert(X[i]);
// for(int i = 0; i <= id; ++i){
// p = k = i;
// cerr << query(1, 1, n) << " ";
// }
// cerr << "\n";
p = 0, k = id;
res[i] = query(1, 1, id);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
50768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
