結果

問題 No.961 Vibrant Fillumination
ユーザー pekempeypekempey
提出日時 2019-12-24 12:40:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 678 ms / 5,000 ms
コード長 3,387 bytes
コンパイル時間 2,395 ms
コンパイル使用メモリ 192,396 KB
実行使用メモリ 9,288 KB
最終ジャッジ日時 2024-09-22 17:14:32
合計ジャッジ時間 34,160 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 = 2000;
vector<pair<int, int>> tmp;
for (int i = 0; i < N; i++) {
tmp.emplace_back(A[i], i + N);
tmp.emplace_back(C[i], i);
}
sort(tmp.begin(), tmp.end());
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<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;
}
}
vector<pair<int, int>> events;
for (auto t : tmp) {
if (used[t.second % N]) {
events.push_back(t);
}
}
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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0