結果

問題 No.961 Vibrant Fillumination
ユーザー pekempeypekempey
提出日時 2019-12-24 12:32:20
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1,462 ms
8,040 KB
testcase_03 AC 1,301 ms
7,628 KB
testcase_04 AC 1,364 ms
8,164 KB
testcase_05 AC 1,164 ms
7,524 KB
testcase_06 AC 1,483 ms
8,216 KB
testcase_07 AC 1,440 ms
8,164 KB
testcase_08 AC 1,489 ms
8,232 KB
testcase_09 AC 1,476 ms
8,040 KB
testcase_10 AC 1,568 ms
8,164 KB
testcase_11 AC 1,626 ms
8,160 KB
testcase_12 AC 1,545 ms
8,040 KB
testcase_13 AC 1,425 ms
8,036 KB
testcase_14 AC 1,680 ms
8,292 KB
testcase_15 AC 1,302 ms
7,500 KB
testcase_16 AC 1,640 ms
8,288 KB
testcase_17 AC 1,365 ms
8,164 KB
testcase_18 AC 1,572 ms
8,420 KB
testcase_19 AC 1,549 ms
8,292 KB
testcase_20 AC 1,573 ms
8,144 KB
testcase_21 AC 1,579 ms
8,168 KB
testcase_22 AC 1,582 ms
8,164 KB
testcase_23 AC 1,328 ms
7,496 KB
testcase_24 AC 1,314 ms
7,500 KB
testcase_25 AC 1,533 ms
8,116 KB
testcase_26 AC 1,227 ms
7,496 KB
testcase_27 AC 1,272 ms
7,620 KB
testcase_28 AC 1,678 ms
8,420 KB
testcase_29 AC 1,814 ms
8,548 KB
testcase_30 AC 710 ms
7,496 KB
testcase_31 AC 1,298 ms
8,548 KB
testcase_32 AC 1,348 ms
8,420 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 1,505 ms
8,168 KB
testcase_35 AC 1,539 ms
8,236 KB
testcase_36 AC 1,469 ms
8,164 KB
testcase_37 AC 1,369 ms
8,040 KB
testcase_38 AC 1,590 ms
8,292 KB
testcase_39 AC 1,254 ms
7,496 KB
testcase_40 AC 1,563 ms
8,044 KB
testcase_41 AC 1,335 ms
8,164 KB
testcase_42 AC 1,499 ms
8,168 KB
testcase_43 AC 1,457 ms
8,040 KB
testcase_44 AC 1,495 ms
8,040 KB
testcase_45 AC 1,524 ms
8,292 KB
testcase_46 AC 1,527 ms
8,044 KB
testcase_47 AC 1,288 ms
7,492 KB
testcase_48 AC 1,269 ms
7,492 KB
testcase_49 AC 1,469 ms
8,036 KB
権限があれば一括ダウンロードができます

ソースコード

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 = 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';
  }
}
0