이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
i64 a[300005];
struct Tree {
const i64 INF = 1e18;
struct Data {
i64 lf, rg, ans;
};
vector<Data> st;
Tree (int _N) : st(4 * _N + 4) {}
Data combine(Data lf, Data rg) {
Data res;
res.lf = lf.lf;
res.rg = rg.rg;
res.ans = lf.ans + rg.ans + (lf.rg > rg.lf);
return res;
}
void build(int id, int l, int r, vector<int> a) {
if (l == r) {
st[id].lf = st[id].rg = a[l - 1];
st[id].ans = 0;
return;
}
int mid = (l + r)/2;
build(id * 2, l, mid, a);
build(id * 2 + 1, mid + 1, r, a);
st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int p, i64 x) {
if (p < l || p > r) return;
if (l == r) {
st[id].lf = st[id].rg = x;
st[id].ans = 0;
return;
}
int mid = (l + r)/2;
update(id * 2, l, mid, p, x);
update(id * 2 + 1, mid + 1, r, p, x);
st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
Data get(int id, int l, int r, int u, int v) {
if (v < l || u > r) return {-INF, INF, 0};
if (u <= l && r <= v) return st[id];
int mid = (l + r)/2;
return combine(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int N = a.size();
int Q = x.size();
Tree T(N + 2);
vector<int> ans;
T.build(1, 1, N, a);
for (int i = 0; i < Q; i ++) {
a[++ x[i]] = v[i];
T.update(1, 1, N, x[i], a[x[i]]);
ans.pb(T.st[1].ans);
}
return ans;
}
void Solve(void) {
// int N, Q; cin >> N >> Q;
// Tree T(N + 2);
// for (int i = 1; i <= N; i ++) cin >> a[i];
// T.build(1, 1, N);
// // cout << T.st[1].ans << "\n";
// while (Q --) {
// int x, v; cin >> x >> v;
// a[++ x] = v;
// T.update(1, 1, N, x, a[x]);
// // cout << x << " " << a[x] << "\n";
// cout << T.st[1].ans << "\n";
// }
}
// signed main() {
// ios_base::sync_with_stdio(false); cin.tie(0);
// cout << fixed << setprecision(10);
// int Tests = 1; // cin >> Tests;
// while (Tests --) {
// Solve();
// }
// }
# | 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... |