#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
constexpr int maxn = 1<<20, B = 2010, inf = 0x3f3f3f3f; // subtasks brutao, mudar
struct SegmentTree {
int tree[maxn], lazy[maxn], a[maxn];
void flush(int node, int i, int j) {
if(!lazy[node]) return;
if(i != j) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0;
}
void build(int node, int i, int j) {
lazy[node] = 0;
if(i == j) return (void)(tree[node] = a[i]);
int m = (i+j) >> 1;
build(node<<1, i, m);
build(node<<1|1, m+1, j);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
void upd(int node, int i, int j, int l, int r, int v) {
flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
lazy[node] += v;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(node<<1, i, m, l, r, v);
upd(node<<1|1, m+1, j, l, r, v);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
int query() { return tree[1] + lazy[1]; } // quero o maximo geral mesmo
} seg;
void compress(vector<int>& A, vector<int>& V) {
map<int,int> mp;
for(int x : A)
mp[x] = 0;
for(int x : V)
mp[x] = 0;
int coord = 0;
for(auto& it : mp)
it.second = ++coord;
for(int& x : A)
x = mp[x];
for(int& x : V)
x = mp[x];
}
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x > 0; x -= x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(; x < maxn; x += x&-x)
ans += bit[x];
return ans;
}
void clear() { memset(bit, 0, sizeof bit); }
} bit;
vector<int> pareto;
int ans[maxn]; bool foi[maxn];
vector<pair<int,int>> qr[maxn];
int FORA[maxn], DENTRO[maxn], FORA_INI[maxn];
void rebuild(const vector<int>& A) {
pareto.clear();
int N = (int)(A.size());
for(int i = 0; i < N; i++) {
if(foi[i]) continue;
while(pareto.size() && A[i] <= A[pareto.back()])
pareto.pop_back();
pareto.push_back(i);
}
bit.clear();
for(int i = 0; i < (int)A.size(); i++) {
while(qr[i].size()) {
auto [val, id] = qr[i].back();
qr[i].pop_back();
ans[id] = bit.query(val+1);
}
DENTRO[i] = bit.query(A[i]+1);
if(!foi[i]) seg.a[i] = DENTRO[i];
else seg.a[i] = -inf;
bit.upd(A[i], 1);
}
seg.build(1, 0, N-1);
}
int bs(int x, const vector<int>& A) {
int l = 0, r = (int)(pareto.size())-1, ans = -1;
while(l <= r) {
int m = (l+r) >> 1;
if(A[pareto[m]] < x)
ans = pareto[m], l = m+1;
else
r = m-1;
}
return ans;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q = (int)X.size(), N = (int)A.size();
compress(A, V);
std::vector<int> answer(Q);
for(int q = 0; q < Q; q += B) {
vector<int> special;
for(int add = 0; add < B && add+q < Q; add++) {
qr[X[q+add]].push_back({V[q+add], q+add});
if(foi[X[q+add]]) continue;
foi[X[q+add]] = 1;
special.push_back(X[q+add]);
}
rebuild(A);
for(int x : special)
FORA[x] = 0;
for(int x : special)
for(int y : special)
if(x < y && A[x] > A[y]) ++FORA[y];
for(int x : special)
DENTRO[x] -= FORA[x], FORA_INI[x] = FORA[x];
for(int add = 0; add < B && add+q < Q; add++) {
int pos = X[q+add], val = V[q+add];
{
int last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, -1);
for(int x : special) {
if(pos < x && A[pos] > A[x]) --FORA[x];
if(x < pos && A[x] > A[pos]) --FORA[pos];
}
}
A[pos] = val;
DENTRO[pos] = ans[q+add] - FORA_INI[pos];
/* DENTRO[pos] = 0;
for(int j = 0; j < pos; j++)
if(!foi[j] && A[j] > val) DENTRO[pos]++; */
{
int last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, 1);
for(int x : special) {
if(pos < x && A[pos] > A[x]) ++FORA[x];
if(x < pos && A[x] > A[pos]) ++FORA[pos];
}
}
int especiais = 0;
for(int x : special)
especiais = max(especiais, DENTRO[x] + FORA[x]);
answer[q+add] = max(seg.query(), especiais);
}
for(int x : special)
foi[x] = 0;
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
29140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
29140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
30268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
29140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
