結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー | e869120 |
提出日時 | 2019-09-06 22:49:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,613 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 80,188 KB |
実行使用メモリ | 29,612 KB |
最終ジャッジ日時 | 2024-06-24 20:21:07 |
合計ジャッジ時間 | 21,257 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
29,612 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 5 ms
13,900 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | TLE | - |
testcase_13 | WA | - |
testcase_14 | TLE | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; #pragma warning (disable: 4996) const int BACKET = 300; long long N, Q, A[1 << 18], T[1 << 18], L[1 << 18], R[1 << 18], X[1 << 18], ans[1 << 18]; bool used[1 << 15]; long long val[1 << 15], v_max[1 << 15], v_sum[1 << 15]; long long gcd(long long a, long long b) { if (b == 0) return a; return gcd(b, a % b); } void ranged(int l, int r) { // 分割 vector<long long> C; for (int i = l; i < r; i++) { C.push_back(L[i]); C.push_back(R[i]); } sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end()); // 初期化 for (int i = 0; i < C.size(); i++) { used[i] = false; val[i] = 0; v_max[i] = 0; v_sum[i] = 0; } for (int i = 0; i < C.size() - 1; i++) { for (int j = C[i]; j < C[i + 1]; j++) { v_max[i] = max(v_max[i], A[j]); v_sum[i] += A[j]; } } // クエリに答える for (int i = l; i < r; i++) { int pos1 = lower_bound(C.begin(), C.end(), L[i]) - C.begin(); int pos2 = lower_bound(C.begin(), C.end(), R[i]) - C.begin(); // 置換 if (T[i] == 1) { for (int j = pos1; j < pos2; j++) { used[j] = true; val[j] = X[i]; } } // gcd if (T[i] == 2) { for (int j = pos1; j < pos2; j++) { if (used[j] == true) { val[j] = gcd(val[j], X[i]); } if (used[j] == false) { long long e = gcd(val[j], X[i]); if (e == val[j]) continue; val[j] = e; v_max[j] = 0; v_sum[j] = 0; for (int k = C[j]; k < C[j + 1]; k++) { long long ee = gcd(e, A[k]); v_max[j] = max(v_max[j], ee); v_sum[j] += ee; } } } } // max を求める if (T[i] == 3) { for (int j = pos1; j < pos2; j++) { if (used[j] == true) ans[i] = max(ans[i], val[j]); else ans[i] = max(ans[i], v_max[j]); } } // 総和を求める if (T[i] == 4) { for (int j = pos1; j < pos2; j++) { if (used[j] == true) ans[i] += 1LL * (C[j + 1] - C[j]) * val[j]; else ans[i] += v_sum[j]; } } } // 更新 for (int i = 0; i < C.size() - 1; i++) { for (int j = C[i]; j < C[i + 1]; j++) { if (used[i] == true) A[i] = val[i]; else A[i] = gcd(val[i], A[i]); } } } int main() { scanf("%lld%lld", &N, &Q); for (int i = 1; i <= N; i++) scanf("%lld", &A[i]); for (int i = 1; i <= Q; i++) { scanf("%lld%lld%lld", &T[i], &L[i], &R[i]); R[i]++; if (T[i] == 1 || T[i] == 2) scanf("%lld", &X[i]); } for (int i = 1; i <= Q; i += BACKET) { int cl = i, cr = i + BACKET; cr = min(cr, (int)Q + 1); ranged(cl, cr); } for (int i = 1; i <= Q; i++) { if (T[i] == 3 || T[i] == 4) printf("%lld\n", ans[i]); } return 0; }