結果
問題 | No.961 Vibrant Fillumination |
ユーザー |
|
提出日時 | 2019-12-24 12:32:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,814 ms / 5,000 ms |
コード長 | 3,311 bytes |
コンパイル時間 | 2,393 ms |
コンパイル使用メモリ | 191,788 KB |
実行使用メモリ | 8,548 KB |
最終ジャッジ日時 | 2024-09-22 17:13:27 |
合計ジャッジ時間 | 74,776 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int N; cin >> N;vector<ll> H(N);for (int i = 0; i < N; i++) {cin >> H[i];}vector<int> A(N), B(N), C(N), D(N), E(N);for (int i = 0; i < N; i++) {cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];E[i]--;}int Q; cin >> Q;vector<int> X(Q), Y(Q);for (int i = 0; i < Q; i++) {cin >> X[i] >> Y[i];}vector<pair<int, int>> ord;enum { DEL, INS, QRY };for (int i = 0; i < N; i++) {ord.emplace_back(DEL, i);ord.emplace_back(INS, i);}for (int i = 0; i < Q; i++) {ord.emplace_back(QRY, i);}auto get_y = [&](pair<int, int> a) {if (a.first == DEL) return D[a.second];if (a.first == INS) return B[a.second];if (a.first == QRY) return Y[a.second];abort();};sort(ord.begin(), ord.end(), [&](pair<int, int> i, pair<int, int> j) {if (get_y(i) != get_y(j)) return get_y(i) < get_y(j);return i.first < j.first;});constexpr int S = 500;vector<ll> ans(Q);for (int l = 0; l < ord.size(); l += S) {int r = min<int>(ord.size(), l + S);int y = get_y(ord[l]);vector<pair<int, int>> events;vector<bool> used(N);for (int i = 0; i < l; i++) {if (ord[i].first == INS) {used[ord[i].second] = true;}if (ord[i].first == DEL) {used[ord[i].second] = false;}}for (int i = 0; i < N; i++) {if (used[i]) {events.emplace_back(A[i], i + N);events.emplace_back(C[i], i);}}sort(events.begin(), events.end());vector<int> cnt(N);ll hassyu = 0;int k = 0;vector<int> queries;for (int i = l; i < r; i++) {if (ord[i].first == QRY) {queries.push_back(i);}}sort(queries.begin(), queries.end(), [&](int i, int j) {return X[ord[i].second] < X[ord[j].second];});for (int i : queries) {int q = ord[i].second;ll x = X[q];while (k < events.size() and events[k].first <= x) {if (events[k].second < N) {int id = events[k].second;if (--cnt[E[id]] == 0) hassyu ^= H[E[id]];} else {int id = events[k].second - N;if (cnt[E[id]]++ == 0) hassyu ^= H[E[id]];}k++;}for (int j = l; j < i; j++) {if (ord[j].first == INS) {int id = ord[j].second;if (A[id] <= x and x < C[id]) {if (cnt[E[id]]++ == 0) hassyu ^= H[E[id]];}}if (ord[j].first == DEL) {int id = ord[j].second;if (A[id] <= x and x < C[id]) {if (--cnt[E[id]] == 0) hassyu ^= H[E[id]];}}}ans[q] = hassyu;for (int j = i - 1; j >= l; j--) {if (ord[j].first == INS) {int id = ord[j].second;if (A[id] <= x and x < C[id]) {if (--cnt[E[id]] == 0) hassyu ^= H[E[id]];}}if (ord[j].first == DEL) {int id = ord[j].second;if (A[id] <= x and x < C[id]) {if (cnt[E[id]]++ == 0) hassyu ^= H[E[id]];}}}}}for (int i = 0; i < Q; i++) {cout << ans[i] << '\n';}}