結果
問題 | No.2311 [Cherry 5th Tune] Cherry Month |
ユーザー | square1001 |
提出日時 | 2023-03-24 23:20:48 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,288 bytes |
コンパイル時間 | 1,585 ms |
コンパイル使用メモリ | 94,336 KB |
実行使用メモリ | 817,872 KB |
最終ジャッジ日時 | 2024-12-15 18:59:03 |
合計ジャッジ時間 | 22,645 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 301 ms
69,468 KB |
testcase_28 | AC | 310 ms
69,472 KB |
testcase_29 | AC | 297 ms
69,472 KB |
testcase_30 | MLE | - |
testcase_31 | MLE | - |
testcase_32 | MLE | - |
testcase_33 | AC | 245 ms
51,912 KB |
testcase_34 | AC | 251 ms
52,748 KB |
testcase_35 | AC | 224 ms
52,496 KB |
testcase_36 | AC | 281 ms
54,120 KB |
testcase_37 | AC | 283 ms
53,500 KB |
testcase_38 | AC | 282 ms
53,876 KB |
testcase_39 | AC | 283 ms
53,952 KB |
testcase_40 | AC | 279 ms
53,204 KB |
testcase_41 | AC | 289 ms
53,624 KB |
testcase_42 | AC | 285 ms
52,756 KB |
testcase_43 | AC | 315 ms
54,068 KB |
testcase_44 | AC | 285 ms
54,908 KB |
testcase_45 | AC | 274 ms
54,936 KB |
testcase_46 | AC | 198 ms
46,948 KB |
testcase_47 | AC | 500 ms
54,356 KB |
testcase_48 | AC | 361 ms
52,108 KB |
testcase_49 | AC | 368 ms
51,880 KB |
testcase_50 | AC | 238 ms
53,144 KB |
ソースコード
#include <vector> #include <iostream> #include <algorithm> using namespace std; class query { public: int tp, t, x, y; query() : tp(-1), t(-1), x(-1), y(-1) {} query(int tp_, int t_, int x_, int y_) : tp(tp_), t(t_), x(x_), y(y_) {} bool operator<(const query& q) const { return t < q.t; } }; int main() { // step #1. input cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<long long> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } int M; cin >> M; vector<query> qs(M); for (int i = 0; i < M; i++) { int tp, x, y; cin >> tp >> x >> y; qs[i] = query(tp, i * 2 + 1, x - 1, tp == 1 ? y - 1 : y); } int Q; cin >> Q; qs.resize(M + Q); for (int i = 0; i < Q; i++) { int t, x; cin >> t >> x; qs[M + i] = query(5, t * 2, x - 1, i); } sort(qs.begin(), qs.end()); // step #2. renumber vertices vector<vector<int> > group(N); vector<int> root(N), id(N), idl(N), idr(N); for (int i = 0; i < N; i++) { group[i] = { i }; root[i] = i; id[i] = i; } for (query q : qs) { if (q.tp == 1) { int rx = root[q.x]; int ry = root[q.y]; if (rx != ry) { if (group[rx].size() < group[ry].size()) { swap(rx, ry); } group[rx].insert(group[rx].end(), group[ry].begin(), group[ry].end()); int delta = idr[rx] - idl[rx]; for (int j : group[ry]) { id[j] += delta; } idl[ry] += delta; idr[ry] += delta; for (int j : group[ry]) { root[j] = rx; } } } } for (query &q : qs) { if (q.tp == 1) { q.x = id[q.x]; q.y = id[q.y]; } else { q.x = id[q.x]; } } vector<long long> TA = A; for (int i = 0; i < N; i++) { A[id[i]] = TA[i]; } // step #3. find left/right of update queries for (int i = 0; i < N; i++) { group[i] = { i }; root[i] = i; idl[i] = i; idr[i] = i + 1; } vector<int> l(M + Q, -1), r(M + Q, -1); for (int i = 0; i < M + Q; i++) { query q = qs[i]; if (q.tp == 1) { int rx = root[q.x]; int ry = root[q.y]; if (rx != ry) { if (group[rx].size() < group[ry].size()) { swap(rx, ry); } group[rx].insert(group[rx].end(), group[ry].begin(), group[ry].end()); int delta = idr[rx] - idl[rx]; idl[rx] = min(idl[rx], idl[ry]); idr[rx] = max(idr[rx], idr[ry]); for (int j : group[ry]) { root[j] = rx; } } } if (q.tp == 4) { l[i] = idl[root[q.x]]; r[i] = idr[root[q.x]]; } } // step #4. find all high-degree vertices vector<int> deg(N, 0); for (query q : qs) { if (q.tp == 1) { deg[q.x] += 1; deg[q.y] += 1; } } int Z = 0; vector<int> vert_id(N, -1); for (int i = 0; i < N; i++) { if (1LL * deg[i] * deg[i] >= N) { vert_id[i] = Z; Z += 1; } } vector<vector<int> > flag(N, vector<int>(Z, -1)); // step #5. binary indexed tree vector<long long> bit(N + 1); auto add = [&](int pos, int val) { for (int i = pos + 1; i <= N; i += i & (-i)) { bit[i] += val; } }; auto getsum = [&](int pos) { long long answer = 0; for (int i = pos; i >= 1; i -= i & (-i)) { answer += bit[i]; } return answer; }; // step #6. process queries vector<vector<int> > g(N); vector<long long> val(N, 0), answer(Q, -1); vector<vector<long long> > bigval(M + Q + 1); bigval[0] = vector<long long>(Z, 0); for (int i = 0; i < M + Q; i++) { bigval[i + 1] = bigval[i]; query q = qs[i]; if (q.tp == 1) { if (vert_id[q.x] == -1) { g[q.x].push_back(q.y); } else if (flag[q.y][vert_id[q.x]] == -1) { flag[q.y][vert_id[q.x]] = i; } if (vert_id[q.y] == -1) { g[q.y].push_back(q.x); } else if (flag[q.x][vert_id[q.y]] == -1) { flag[q.x][vert_id[q.y]] = i; } } if (q.tp == 2) { val[q.x] += q.y; } if (q.tp == 3) { if (vert_id[q.x] == -1) { for (int j : g[q.x]) { val[j] += q.y; } } else { bigval[i + 1][vert_id[q.x]] += q.y; } val[q.x] += q.y; } if (q.tp == 4) { add(l[i], q.y); add(r[i], -q.y); } if (q.tp == 5) { long long subval = val[q.x]; for (int j = 0; j < Z; j++) { if (flag[q.x][j] != -1) { subval += bigval[i + 1][j] - bigval[flag[q.x][j]][j]; } } subval += getsum(q.x + 1); answer[q.y] = max(A[q.x] - subval, 0LL); } } // step #7. output for (int i = 0; i < Q; i++) { cout << answer[i] << '\n'; } return 0; }