結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-08-12 14:34:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 524 ms / 3,000 ms |
コード長 | 3,255 bytes |
コンパイル時間 | 2,630 ms |
コンパイル使用メモリ | 211,248 KB |
実行使用メモリ | 38,880 KB |
最終ジャッジ日時 | 2024-11-19 20:10:11 |
合計ジャッジ時間 | 11,850 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template <class T> struct fenwick_tree {using U = T;public:fenwick_tree() : _n(0) {}fenwick_tree(int n) : _n(n), data(n) {}void add(int p, T x) {assert(0 <= p && p < _n);p++;while (p <= _n) {data[p - 1] += U(x);p += p & -p;}}T sum(int l, int r) {assert(0 <= l && l <= r && r <= _n);return sum(r) - sum(l);}private:int _n;std::vector<U> data;U sum(int r) {U s = 0;while (r > 0) {s += data[r - 1];r -= r & -r;}return s;}};int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;vector<tuple<string, int, int>> a(n);vector<string> ca(n);vector<int> ct(2 * n);for(int i = 0; i < n; i++){string s;int l, r;cin >> s >> l >> r;a[i] = make_tuple(s, l, r);ca[i] = s;ct[i] = l;ct[i + n] = r;ct.push_back(r + 1);}int Q;cin >> Q;vector<tuple<int, string, int, int>> query(Q);for(int i = 0; i < Q; i++){string s;int cmd, l, r, x;cin >> cmd;if(cmd == 1){cin >> s >> x;ca.push_back(s);query[i] = make_tuple(cmd, s, x, 0);ct.push_back(x);}else if(cmd == 2){cin >> x;query[i] = make_tuple(cmd, "", x, 0);ct.push_back(x);}else if(cmd == 3){cin >> s >> l >> r;query[i] = make_tuple(cmd, s, l, r);ca.push_back(s);ct.push_back(l);ct.push_back(r);ct.push_back(r + 1);}}sort(ca.begin(), ca.end());ca.erase(unique(ca.begin(), ca.end()), ca.end());ct.push_back(0);sort(ct.begin(), ct.end());ct.erase(unique(ct.begin(), ct.end()), ct.end());fenwick_tree<int> fw(ct.size() + 1);vector<set<pair<int,int>>> S(ca.size());for(int i = 0; i < ca.size(); i++) S[i].insert({1 << 30, 1 << 30});auto add = [&](string s, int l, int r){int id = lower_bound(ca.begin(), ca.end(), s) - ca.begin();S[id].insert({r, l});l = lower_bound(ct.begin(), ct.end(), l) - ct.begin();r = lower_bound(ct.begin(), ct.end(), r) - ct.begin();fw.add(l, 1);fw.add(r + 1, -1);};auto search = [&](string s, int t){int id = lower_bound(ca.begin(), ca.end(), s) - ca.begin();auto it = S[id].lower_bound({t, -1});if(it->second <= t && t <= it->first) return true;return false;};for(int i = 0; i < n; i++){string s;int l, r;tie(s, l, r) = a[i];add(s, l, r);}for(int i = 0; i < Q; i++){string s;int cmd, l, r;tie(cmd, s, l, r) = query[i];if(cmd == 1){cout << (search(s, l) ? "Yes" : "No") << '\n';}else if(cmd == 2){int t = lower_bound(ct.begin(), ct.end(), l) - ct.begin();cout << fw.sum(0, t + 1) << '\n';}else{add(s, l, r);}}}