| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1288859 | am_aadvik | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
const int inf = 1e9;
//#define SUBMIT 1
using namespace std;
vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
#ifndef SUBMIT
#include <cstdio>
#include <cstdlib>
#include <vector>
int readInt() {
int i;
if (scanf("%d", &i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return i;
}
int main() {
int N, Q;
N = readInt();
Q = readInt();
std::vector<int> A(N);
for (int i = 0; i < N; i++)
A[i] = readInt();
std::vector<int> X(Q), V(Q);
for (int j = 0; j < Q; j++) {
X[j] = readInt();
V[j] = readInt();
}
std::vector<int> res = countScans(A, X, V);
for (int j = 0; j<int(res.size()); j++)
printf("%d\n", res[j]);
}
#endif
class segtree {
private:
vector<int> st, a, lazy;
int n;
const int dv = -inf;
const int ldv = 0;
void upd(int s, int e, int node, int val) {
if (val == ldv) return;
st[node] += (e - s + 1) * val;
}
int build(int s, int e, int node) {
if (s == e) return st[node] = a[s];
int mid = (s + e) / 2;
return st[node] = max(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
}
int query(int s, int e, int node, int l, int r) {
if ((l <= s) && (r >= e)) return st[node];
if ((r < s) || (l > e)) return dv;
int mid = (s + e) / 2;
return max(query(s, mid, node * 2, l, r), query(mid + 1, e, node * 2 + 1, l, r));
}
void update(int s, int e, int node, int l, int r, int val) {
if ((r < s) || (l > e)) return;
if ((l <= s) && (r >= e)) {
upd(s, e, node, val);
lazy[node] += val;
return;
}
int mid = (s + e) / 2;
upd(s, mid, node * 2, lazy[node]);
upd(mid + 1, e, node * 2 + 1, lazy[node]);
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
lazy[node] = ldv;
update(s, mid, node * 2, l, r, val);
update(mid + 1, e, node * 2 + 1, l, r, val);
st[node] = max(st[node * 2], st[node * 2 + 1]);
}
public:
segtree(int N, vector<int> arr) {
a = arr, n = N;
st.assign(4 * n, dv);
lazy.assign(4 * n, ldv);
build(0, n - 1, 1);
}
int query(int l, int r) {
return query(0, n - 1, 1, l, r);
}
void update(int l, int r, int val) {
update(0, n - 1, 1, l, r, val);
}
};
void iset(int i, vector<vector<int>> &a, segtree &s) {
int idx = a[i][1];
s.update(i, i, idx + inf);
s.update(i + 1, a.size() - 1, -1);
}
void uset(int i, vector<vector<int>>& a, segtree& s) {
int idx = a[i][1];
s.update(i, i, -(idx + inf));
s.update(i + 1, a.size() - 1, +1);
}
vector<int> countScans(vector<int> a, vector<int> qi, vector<int> qv) {
int n = a.size(), q = qi.size();
vector<vector<int>> arr;
vector<int> pq(q), pa(n);
segtree s(n + q, vector<int>(n + q, -inf));
for (int i = 0; i < n; ++i)
arr.push_back({ a[i], i, -1 });
for (int i = 0; i < q; ++i)
arr.push_back({ qv[i], qi[i], i });
sort(arr.begin(), arr.end());
for (int i = 0; i < (n + q); ++i)
if (arr[i][2] != -1) pq[arr[i][2]] = i;
else pa[arr[i][1]] = i;
for (int i = 0; i < arr.size(); ++i)
if (arr[i][2] == -1)
iset(i, arr, s);
vector<int> res;
for (int t = 0; t < q; ++t) {
int idx = pq[t], i = qi[t], v = qv[t];
uset(pa[i], arr, s), iset(idx, arr, s);
int ans = s.query(0, n + q - 1);
res.push_back(ans);
}
return res;;
}