| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1148771 | fzyzzz_z | Event Hopping 2 (JOI21_event2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
const int id = -1e9;
int tree[2 * N], info[2 * N], pos[2 * N];
void init() {
for (int i = 0; i < 2 * N; ++i) {
tree[i] = id;
info[i] = -1;
pos[i] = (i < N ? N - 1 : i - N);
}
}
pair<int, int> query(int l, int r, int L = 0, int R = N - 1, int x = 1) {
if (L > r || l > R) return {id, -1};
if (l <= L && R <= r) return {tree[x], pos[x]};
int M = (L + R) / 2;
auto [a, b] = query(l, r, L, M, 2 * x);
auto [c, d] = query(l, r, L, M + 1, 2 * x + 1);
return ((a > c) ? make_pair(a, b) : make_pair(c, d));
}
void update(int p, int v, int L = 0, int R = N - 1, int x = 1) {
if (L > p || p > R) return;
if (L == p && p == R) {
tree[x] = max(tree[x], v);
return;
}
int M = (L + R) / 2;
update(p, v, L, M, 2 * x);
update(p, v, M + 1, R, 2 * x + 1);
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
pos[x] = (tree[2 * x] > tree[2 * x + 1] ? pos[2 * x] : pos[2 * x + 1]);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<array<int, 3>> a;
vector<int> xs;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
xs.push_back(x);
xs.push_back(y);
a.push_back({x, y, i + 1});
}
a.push_back({-1, -1, 0});
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (auto & [x, y, z]: a) {
x = (int) (lower_bound(xs.begin(), xs.end(), x) - xs.begin());
y = (int) (lower_bound(xs.begin(), xs.end(), y) - xs.begin());
}
int m = xs.size();
sort(a.begin(), a.end(), [](const array<int, 3> & x, const array<int, 3> & y){
return x[0] > y[0];
});
init();
// update(N - 1, 0);
// assert(query(0, N - 1) == make_pair(0, N - 1));
vector<int> amt(m, -1), next(m, -1);
auto chmax = [&] (int i, int x, int y) -> void {
if (x > amt[i]) {
amt[i] = x;
next[i] = y;
} else if ((x == amt[i]) && (y < next[i])) {
next[i] = y;
}
};
for (auto [l, r, i]: a) {
chmax(l, 1, -1);
// auto [x, y] = query()
}
}ce