結果
| 問題 | No.961 Vibrant Fillumination |
| ユーザー |
 square1001
|
| 提出日時 | 2020-01-18 00:56:25 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,815 bytes |
| コンパイル時間 | 1,703 ms |
| コンパイル使用メモリ | 111,280 KB |
| 実行使用メモリ | 814,080 KB |
| 最終ジャッジ日時 | 2024-09-18 20:28:49 |
| 合計ジャッジ時間 | 18,834 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 WA * 1 MLE * 1 -- * 38 |
ソースコード
#include <cmath>#include <vector>#include <cassert>#include <iostream>#include <algorithm>using namespace std;int main() {cin.tie(0);ios_base::sync_with_stdio(false);int N;cin >> N;vector<long long> 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];if (E[i] < 0 || N <= E[i]) {assert(false);}}vector<vector<int> > G(N);for (int i = 0; i < N; ++i) {G[E[i]].push_back(i);}vector<int> perm(N);int active = 0;for (int i = 0; i < N; ++i) {perm[i] = i;if (!G[i].empty()) ++active;}sort(perm.begin(), perm.end(), [&](int i, int j) { return G[i].size() > G[j].size(); });int threshold = int(sqrt(N)) / 4 + 1;int lp = 0, sum = 0, cols = 0;vector<vector<int> > group;vector<int> col;for (int i = 0; i < active; ++i) {sum += G[perm[i]].size();if (sum >= threshold || i == active - 1) {if (lp == i) {int divs = max(int(G[perm[i]].size()) / threshold, 1);for (int j = 0; j < divs; ++j) {int dl = j * G[perm[i]].size() / divs, dr = (j + 1) * G[perm[i]].size() / divs;group.push_back(vector<int>(G[perm[i]].begin() + dl, G[perm[i]].begin() + dr));col.push_back(cols);}}else {group.push_back(vector<int>());for (int j = lp; j <= i; ++j) {group.back().insert(group.back().end(), G[j].begin(), G[j].end());}col.push_back(cols);}sum = 0, lp = i + 1;++cols;}}vector<vector<int> > cpx, cpy; vector<vector<vector<long long> > > dat;for (int i = 0; i < group.size(); ++i) {vector<int> cps, cx = { 0, 2 * N }, cy = { 0, 2 * N };for (int j : group[i]) {cps.push_back(E[j]);cx.push_back(A[j]);cx.push_back(C[j]);cy.push_back(B[j]);cy.push_back(D[j]);}sort(cx.begin(), cx.end());cx.erase(unique(cx.begin(), cx.end()), cx.end());sort(cy.begin(), cy.end());cy.erase(unique(cy.begin(), cy.end()), cy.end());cpx.push_back(cx);cpy.push_back(cy);sort(cps.begin(), cps.end());cps.erase(unique(cps.begin(), cps.end()), cps.end());vector<vector<int> > F(cps.size());for (int j : group[i]) {F[lower_bound(cps.begin(), cps.end(), E[j]) - cps.begin()].push_back(j);}int h = cx.size(), w = cy.size();vector<vector<long long> > subdat(h + 1, vector<long long>(w + 1));for (int j = 0; j < F.size(); ++j) {vector<int> csx, csy;for (int k : F[j]) {csx.push_back(A[k]);csx.push_back(C[k]);csy.push_back(B[k]);csy.push_back(D[k]);}sort(csx.begin(), csx.end());csx.erase(unique(csx.begin(), csx.end()), csx.end());sort(csy.begin(), csy.end());csy.erase(unique(csy.begin(), csy.end()), csy.end());vector<vector<int> > imos(csx.size(), vector<int>(csy.size()));for (int k : F[j]) {int xa = lower_bound(csx.begin(), csx.end(), A[k]) - csx.begin();int ya = lower_bound(csy.begin(), csy.end(), B[k]) - csy.begin();int xb = lower_bound(csx.begin(), csx.end(), C[k]) - csx.begin();int yb = lower_bound(csy.begin(), csy.end(), D[k]) - csy.begin();++imos[xa][ya];++imos[xb][yb];--imos[xa][yb];--imos[xb][ya];}for (int k = 1; k < csx.size(); ++k) {for (int l = 0; l < csy.size(); ++l) {imos[k][l] += imos[k - 1][l];}}for (int k = 0; k < csx.size(); ++k) {for (int l = 1; l < csy.size(); ++l) {imos[k][l] += imos[k][l - 1];}}for (int k = 0; k < csx.size(); ++k) {csx[k] = lower_bound(cx.begin(), cx.end(), csx[k]) - cx.begin();}for (int k = 0; k < csy.size(); ++k) {csy[k] = lower_bound(cy.begin(), cy.end(), csy[k]) - cy.begin();}for (int k = 0; k < csx.size() - 1; ++k) {for (int l = 0; l < csy.size() - 1; ++l) {if (imos[k][l] == 0) continue;subdat[csx[k]][csy[l]] ^= H[cps[j]];subdat[csx[k + 1]][csy[l + 1]] ^= H[cps[j]];subdat[csx[k]][csy[l + 1]] ^= H[cps[j]];subdat[csx[k + 1]][csy[l]] ^= H[cps[j]];}}}for (int j = 1; j < cx.size(); ++j) {for (int k = 0; k < cy.size(); ++k) {subdat[j][k] ^= subdat[j - 1][k];}}for (int j = 0; j < cx.size(); ++j) {for (int k = 1; k < cy.size(); ++k) {subdat[j][k] ^= subdat[j][k - 1];}}dat.push_back(subdat);}int Q;cin >> Q;while (Q--) {int x, y;cin >> x >> y;vector<long long> sub(cols);for (int i = 0; i < group.size(); ++i) {if (sub[col[i]] != 0) continue;int px = lower_bound(cpx[i].begin(), cpx[i].end(), x + 1) - cpx[i].begin() - 1;int py = lower_bound(cpy[i].begin(), cpy[i].end(), y + 1) - cpy[i].begin() - 1;sub[col[i]] = dat[i][px][py];}long long ans = 0;for (int i = 0; i < cols; ++i) {ans ^= sub[i];}cout << ans << '\n';}return 0;}