結果
問題 | No.2933 Range ROT Query |
ユーザー |
![]() |
提出日時 | 2024-10-17 17:30:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 212 ms / 3,000 ms |
コード長 | 1,976 bytes |
コンパイル時間 | 2,143 ms |
コンパイル使用メモリ | 202,828 KB |
最終ジャッジ日時 | 2025-02-24 20:04:43 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } #include <atcoder/fenwicktree> #include <atcoder/lazysegtree> using namespace atcoder; int msk = (1 << 26) - 1; int op(int a, int b) { return a & b; } int e() { return 1; } int mapping(int f, int a) { // left cyclic shift by f return ((a << f) | (a >> (26 - f))) & msk; } int composition(int f, int g) { return (f + g) % 26; } int id() { return 0; } bool f(int x) { return x == 1; } int main() { fast_io(); string s, t; cin >> s >> t; int n = s.size(), m = t.size(); int M = min(n, m); vector<int> seg_data(M); for (int i = 0; i < M; i++) { int diff = (s[i] + 26 - t[i]) % 26; seg_data[i] = 1 << diff; } fenwick_tree<long long> fw(n + 1); { for (int i = 0; i < n; i++) { if (i == 0) { fw.add(i, s[i] - 'a'); } else { fw.add(i, (s[i] + 26 - s[i - 1]) % 26); } } } lazy_segtree<int, op, e, int, mapping, composition, id> seg(seg_data); int q; cin >> q; for (; q--;) { int com; cin >> com; if (com == 1) { int l, r, x; cin >> l >> r >> x; l--; fw.add(l, x); fw.add(r, -x); if (l >= M) { continue; } seg.apply(l, min(r, M), x); } if (com == 2) { int l, r, x; cin >> l >> r >> x; l--; if (l >= M) { continue; } seg.apply(l, min(r, M), 26 - x); } if (com == 3) { int p; cin >> p; int r = seg.max_right<f>(p - 1); if (r < M) { int s = fw.sum(0, r + 1) % 26; int ts = seg.get(r); int diff = -1; for (int i = 0; i < 26; i++) { if ((ts >> i) & 1) { diff = i; break; } } assert(diff != -1); char sr = 'a' + s; char tr = 'a' + (s - diff + 26) % 26; if (sr < tr) { cout << "Lesser\n"; } else { cout << "Greater\n"; } continue; } if (n < m) { cout << "Lesser\n"; } else if (n > m) { cout << "Greater\n"; } else { cout << "Equals\n"; } } } }