結果
問題 |
No.3239 Omnibus
|
ユーザー |
|
提出日時 | 2025-08-21 12:58:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,604 bytes |
コンパイル時間 | 4,358 ms |
コンパイル使用メモリ | 280,976 KB |
実行使用メモリ | 91,736 KB |
最終ジャッジ日時 | 2025-08-21 12:58:50 |
合計ジャッジ時間 | 15,914 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 WA * 29 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; static const ll INF = (numeric_limits<ll>::max() / 10); #define rep(i,n) for (ll i = 0; i < (ll)(n); ++i) #define all(a) (a).begin(), (a).end() using namespace atcoder; struct Node { ll i_sum = 0, cnt_sum = 0; }; Node op(Node a, Node b){ return {a.i_sum + b.i_sum, a.cnt_sum + b.cnt_sum}; } Node e(){ return {0,0}; } enum EventType { ADD, REMOVE, QUERY }; struct Event { ll t; EventType type; ll idx = -1; ll l = -1; ll r = -1; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, q; cin >> n >> q; string s; cin >> s; vector<tuple<ll,ll,ll,string>> queries(q); unordered_map<string, vector<Event>> ump; rep(i,q){ ll t; cin >> t; if(t == 1){ ll k; string x; cin >> k >> x; queries[i] = {t, k-1, -1, x}; }else{ ll l, r; string a; cin >> l >> r >> a; queries[i] = {t, l-1, r, a}; ump[a].push_back({i, QUERY, -1, l-1, r}); } } rep(i, n-2){ string str = s.substr(i,3); auto it = ump.find(str); if(it == ump.end()) continue; it->second.push_back({-1, ADD, i}); it->second.push_back({q , REMOVE, i}); } rep(i,q){ auto [t,a,b,c] = queries[i]; if(t == 1){ ll idx = a; char x = c[0]; for(ll si = max(0LL, idx-2); si <= min(n-3, idx); ++si){ string str = s.substr(si,3); auto it = ump.find(str); if(it != ump.end()) it->second.push_back({i, REMOVE, si}); } s[idx] = x; for(ll si = max(0LL, idx-2); si <= min(n-3, idx); ++si){ string str = s.substr(si,3); auto it = ump.find(str); if(it != ump.end()) it->second.push_back({i, ADD, si}); } } } for(auto &kv : ump){ auto &events = kv.second; sort(all(events), [](const Event& a, const Event& b){ if(a.t != b.t) return a.t < b.t; return a.type < b.type; }); } segtree<Node, op, e> seg(n-2); vector<pair<ll,ll>> t_ans; t_ans.reserve(q); vector<int> touched; touched.reserve(1024); vector<char> seen(n-2, 0); for (auto &kv : ump){ for(int idx : touched){ seg.set(idx, {0,0}); seen[idx] = 0; } touched.clear(); const auto &events = kv.second; for(const auto &ev : events){ if(ev.type == ADD){ int idx = (int)ev.idx; if(!seen[idx]){ seen[idx] = 1; touched.push_back(idx); } seg.set(idx, {idx + 1, 1}); }else if(ev.type == REMOVE){ int idx = (int)ev.idx; seg.set(idx, {0,0}); }else{ ll L = ev.l; ll U = ev.r - 3; if (U >= L){ // 半開区間 [L, U+1) Node res = seg.prod((int)L, (int)(U + 1)); ll ans = res.i_sum - L * res.cnt_sum; // sum((idx+1) - L) t_ans.emplace_back(ev.t, ans); }else{ t_ans.emplace_back(ev.t, 0); } } } } sort(all(t_ans), [](const auto& a, const auto& b){ return a.first < b.first; }); for(auto &p : t_ans) cout << p.second << '\n'; return 0; }