This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int Off = 1 << 20;
struct SegTree {
int a[2 * Off], lazy[2 * Off];
set<int> inds[Off];
void build() {
for (int i = 0; i < Off; i++) {
inds[i].insert(-1e9);
a[i + Off] = *inds[i].rbegin();
}
for (int i = Off - 1; i > 0; i--)
a[i] = max(a[2 * i], a[2 * i + 1]);
}
void propagate(int i) {
a[i] += lazy[i];
if (i < Off) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
void update_path(int j, int i = 1, int lo = 0, int hi = Off) {
propagate(i);
if (lo + 1 == hi) return;
int mid = (lo + hi) / 2;
if (j < mid) update_path(j, 2 * i, lo, mid);
else update_path(j, 2 * i + 1, mid, hi);
a[i] = max(a[2 * i], a[2 * i + 1]);
}
void update_inds(int i, int ind, bool add) {
a[i + Off] -= *inds[i].rbegin();
if (add) inds[i].insert(ind);
else inds[i].erase(ind);
a[i + Off] += *inds[i].rbegin();
update_path(i);
}
void update_segment(int l, int r, int val, int i = 1, int lo = 0, int hi = Off) {
if (r <= lo || hi <= l) return;
if (l <= lo && hi <= r) {
lazy[i] += val;
propagate(i);
} else {
propagate(i);
int mid = (lo + hi) / 2;
update_segment(l, r, val, 2 * i, lo, mid);
update_segment(l, r, val, 2 * i + 1, mid, hi);
a[i] = max(a[2 * i], a[2 * i + 1]);
}
}
void update_segment(int i, bool add) {
if (add) update_segment(i + 1, Off, -1);
else update_segment(i + 1, Off, 1);
}
int query() {
propagate(1);
return a[1];
}
} T;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
int n = a.size(), q = x.size();
vector<int> answer(q);
vector<int> val;
map<int, int> compress;
for (int i : a) val.push_back(i);
for (int i : v) val.push_back(i);
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 0; i < (int)val.size(); i++)
compress[val[i]] = i;
for (int i = 0; i < n; i++)
T.inds[compress[a[i]]].insert(i);
T.build();
for (int i = 0; i < n; i++)
T.update_segment(compress[a[i]], true);
for (int i = 0; i < q; i++) {
T.update_inds(compress[a[x[i]]], x[i], false);
T.update_segment(compress[a[x[i]]], false);
T.update_inds(compress[v[i]], x[i], true);
T.update_segment(compress[v[i]], true);
answer[i] = T.query();
a[x[i]] = v[i];
}
return answer;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |