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 <bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
#define lmn LLONG_MIN
#define lmx LLONG_MAX
#define imn INT_MIN
#define imx INT_MAX
using namespace std;
const ll mod = 1e9 + 7;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag, tree_order_statistics_node_update>
int n, m;
// segtree implementation begins here
vector<int> st, lazy;
void pd(int id, int l, int mid, int r) {
st[lid] += lazy[id];
st[rid] += lazy[id];
lazy[lid] += lazy[id];
lazy[rid] += lazy[id];
lazy[id] = 0;
}
void update(int id, int l, int r, int ul, int ur, int val) {
if (r < ul or l > ur) return;
if (ul <= l and r <= ur) {
st[id] += val;
lazy[id] += val;
return;
}
int mid = (l + r) / 2;
pd(id, l, mid, r);
update(lid, l, mid, ul, ur, val);
update(rid, mid + 1, r, ul, ur, val);
st[id] = max(st[lid], st[rid]);
}
void setas(int id, int l, int r, int pos, int val) {
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) / 2;
pd(id, l, mid, r);
if (mid <= pos) setas(lid, l, mid, pos, val);
else setas(rid, mid + 1, r, pos, val);
st[id] = max(st[lid], st[rid]);
}
// segtree implementations ends here
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
int q = X.size(), i;
vector<ll> a(n);
for (i = 0; i < n; i++) a[i] = A[i] * 1000000ll + i;
unordered_map<ll, int> b2s;
vector<ll> s2b = a;
for (i = 0; i < q; i++) s2b.push_back(V[i] * 1000000ll + X[i]);
sort(s2b.begin(), s2b.end());
for (i = 0; i < n + q; i++) b2s[s2b[i]] = i;
m = s2b.size();
st.resize(m * 4);
lazy.resize(m * 4);
ordered_set os;
for (ll elem : a) os.insert(elem);
for (i = 0; i < n; i++) setas(0, 0, m - 1, i, i - os.order_of_key(a[i]));
vector<int> ans(q);
for (i = 0; i < q; i++) {
update(0, 0, m - 1, b2s[a[X[i]]] + 1, m - 1, 1);
os.erase(a[X[i]]);
a[X[i]] = V[i] * 1000000ll + X[i];
os.insert(a[X[i]]);
setas(0, 0, m - 1, X[i], X[i] - os.order_of_key(a[X[i]]));
update(0, 0, m - 1, b2s[a[X[i]]] + 1, m - 1, -1);
ans[i] = st[0];
}
return ans;
}
# | 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... |