結果
問題 | No.2311 [Cherry 5th Tune] Cherry Month |
ユーザー |
![]() |
提出日時 | 2023-03-25 12:42:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 7,890 bytes |
コンパイル時間 | 2,263 ms |
コンパイル使用メモリ | 132,384 KB |
実行使用メモリ | 814,692 KB |
最終ジャッジ日時 | 2024-12-15 19:02:38 |
合計ジャッジ時間 | 24,151 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 MLE * 3 |
ソースコード
#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;}};vector<long long> solve(int N, int M, int Q, const vector<long long>& TA, const vector<int>& TP, const vector<int>& X, const vector<int>& Y, constvector<int>& S, const vector<int>& I) {// step #1. preparationvector<query> qs(M + Q);for (int i = 0; i < M; i++) {qs[i] = query(TP[i], i * 2 + 1, X[i], Y[i]);}for (int i = 0; i < Q; i++) {qs[M + i] = query(5, S[i] * 2, I[i], i);}sort(qs.begin(), qs.end());// step #2. renumber verticesvector<vector<int> > group(N);vector<int> root(N), id(N), sz(N);for (int i = 0; i < N; i++) {group[i] = { i };root[i] = i;id[i] = 0;sz[i] = 1;}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());for (int j : group[ry]) {id[j] += sz[rx];}sz[rx] += sz[ry];for (int j : group[ry]) {root[j] = rx;}group[ry].clear();}}}int offset = 0;for (int i = 0; i < N; i++) {for (int j : group[i]) {id[j] += offset;}offset += group[i].size();}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> A(N);for (int i = 0; i < N; i++) {A[id[i]] = TA[i];}// step #3. find left/right of update queriesvector<int> idl(N), idr(N);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());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 verticesvector<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 treevector<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 queriesvector<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);}}return answer;}vector<long long> solve_easy(int N, int M, int Q, const vector<long long>& TA, const vector<int>& TP, const vector<int>& X, const vector<int>& Y,const vector<int>& S, const vector<int>& I) {// step #1. preparationvector<query> qs(M + Q);for (int i = 0; i < M; i++) {qs[i] = query(TP[i], i * 2 + 1, X[i], Y[i]);}for (int i = 0; i < Q; i++) {qs[M + i] = query(5, S[i] * 2, I[i], i);}sort(qs.begin(), qs.end());// step #2. renumber verticesvector<long long> A = TA;vector<long long> answer(Q, -1);vector<vector<int> > g(N);for (query q : qs) {if (q.tp == 1) {g[q.x].push_back(q.y);g[q.y].push_back(q.x);}if (q.tp == 2) {A[q.x] = max(A[q.x] - q.y, 0LL);}if (q.tp == 3) {A[q.x] = max(A[q.x] - q.y, 0LL);for (int i : g[q.x]) {A[i] = max(A[i] - q.y, 0LL);}}if (q.tp == 4) {vector<bool> vis(N, false);auto dfs = [&](auto& self, int pos) -> void {vis[pos] = true;A[pos] = max(A[pos] - q.y, 0LL);for (int i : g[pos]) {if (!vis[i]) {self(self, i);}}};dfs(dfs, q.x);}if (q.tp == 5) {answer[q.y] = A[q.x];}}return answer;}#include <set>#include <random>#include <string>mt19937_64 mt(1);int rand_int(int l, int r) {return l + int(mt() % (r - l));}template<class T> string to_string(const vector<T>& arr) {string res = "[";for (int i = 0; i < int(arr.size()); i++) {if (i != 0) {res += ", ";}res += std::to_string(arr[i]);}res += "]";return res;}bool checker(int N) {const int samples = 10000;for (int id = 1; id <= samples; id++) {vector<long long> A(N);for (int i = 0; i < N; i++) {A[i] = 99;}int M = 2 * N;set<pair<int, int> > s;vector<int> TP(M), X(M), Y(M);for (int i = 0; i < M; i++) {TP[i] = rand_int(s.size() != N * (N - 1) / 2 ? 1 : 2, 5);X[i] = rand_int(0, N);if (TP[i] == 1) {do {X[i] = rand_int(0, N);Y[i] = rand_int(0, N);} while (X[i] == Y[i] || s.find(make_pair(min(X[i], Y[i]), max(X[i], Y[i]))) != s.end());s.insert(make_pair(min(X[i], Y[i]), max(X[i], Y[i])));}else {X[i] = rand_int(0, N);Y[i] = rand_int(1, 10);}}int Q = 1;vector<int> S(Q), I(Q);for (int i = 0; i < Q; i++) {S[i] = rand_int(0, M + 1);I[i] = rand_int(0, N);}vector<long long> res1 = solve(N, M, Q, A, TP, X, Y, S, I);vector<long long> res2 = solve_easy(N, M, Q, A, TP, X, Y, S, I);if (res1 != res2) {cout << "N = " << N << ", M = " << M << ", Q = " << Q << ", Case #" << id << ":" << endl;cout << "A = " << to_string(A) << endl;cout << "TP= " << to_string(TP) << endl;cout << "X = " << to_string(X) << endl;cout << "Y = " << to_string(Y) << endl;cout << "S = " << to_string(S) << endl;cout << "I = " << to_string(I) << endl;cout << "Returns: " << to_string(res1) << endl;cout << "Answer: " << to_string(res2) << endl;return false;}}return true;}int main() {/*for (int N = 2; N <= 10; N++) {if (!checker(N)) {break;}cout << "N = " << N << " Complete!" << endl;}*/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<int> TP(M), X(M), Y(M);for (int i = 0; i < M; i++) {cin >> TP[i] >> X[i] >> Y[i];X[i] -= 1;Y[i] -= (TP[i] == 1 ? 1 : 0);}int Q;cin >> Q;vector<int> S(Q), I(Q);for (int i = 0; i < Q; i++) {cin >> S[i] >> I[i];I[i] -= 1;}vector<long long> answer = solve(N, M, Q, A, TP, X, Y, S, I);for (int i = 0; i < Q; i++) {cout << answer[i] << '\n';}return 0;}