結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-07-20 14:58:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 693 ms / 3,000 ms |
コード長 | 5,068 bytes |
コンパイル時間 | 3,264 ms |
コンパイル使用メモリ | 230,732 KB |
最終ジャッジ日時 | 2025-02-15 15:53:49 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>struct BinaryIndexedTree{int N;vector<T> BIT;BinaryIndexedTree(const int &N): N(N), BIT(N + 1, 0){}T get(int i){return sum(i + 1) - sum(i);}void add(int i, T x){i++;while(i <= N){BIT[i] += x;i += i & -i;}}T sum(int i) const {T ans = 0;while(i > 0){ans += BIT[i];i -= i & -i;}return ans;}T sum(int L, int R) const {return sum(R) - sum(L);}int lower_bound(T x) const {if(x <= 0){return 0;}else{int v = 0, r = 1;while(r < N) r = r << 1;for(int len = r; len > 0; len = len >> 1){if(v + len < N && BIT[v + len] < x){x -= BIT[v + len];v += len;}}return v;}}int upper_bound(T x) const {if(x < 0){return 0;}else{int v = 0, r = 1;while(r <= N) r = r << 1;for(int len = r; len > 0; len = len >> 1){if(v + len <= N && BIT[v + len] <= x){x -= BIT[v + len];v += len;}}return v;}}T operator [](int i) const {return sum(i, i + 1);}};template <typename T>struct compress{vector<T> sorted, compressed;compress(const vector<T>& vec){int n = vec.size();compressed.resize(n);for(T x : vec){sorted.emplace_back(x);}sort(sorted.begin(), sorted.end());sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());for(int i = 0; i < n; ++i){compressed[i] = lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();}}int get(const T& x) const{return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();}T inv(const T& x) const{return sorted[x];}size_t size() const{return sorted.size();}vector<T> getCompressed() const{return compressed;}};int conv(string s){int res = 0, n = s.size();int p = 1;for(int i = 0; i < n; i++){res += (s[i] - 'A' + 1) * p;p *= 27;}return res;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N; cin >> N;map<int, vector<int>> time;vector<string> X(N);vector<int> XC(N), L(N), R(N);vector<int> XCC = {0};for(int i = 0; i < N; i++){cin >> X[i] >> L[i] >> R[i];XC[i] = conv(X[i]);time[0].push_back(L[i]);time[0].push_back(R[i] + 1);time[XC[i]].push_back(L[i]);time[XC[i]].push_back(R[i] + 1);XCC.push_back(XC[i]);}int Q; cin >> Q;vector<tuple<int, int, int, int>> query(Q);for(int i = 0; i < Q; i++){int type; cin >> type;if(type == 1){string x; int t; cin >> x >> t;int xc = conv(x);query[i] = {type, xc, t, 0};time[xc].push_back(t);XCC.push_back(xc);}else if(type == 2){int t; cin >> t;query[i] = {type, t, 0, 0};time[0].push_back(t);}else{string x; int l, r; cin >> x >> l >> r;int xc = conv(x);query[i] = {type, xc, l, r};time[0].push_back(l);time[0].push_back(r + 1);time[xc].push_back(l);time[xc].push_back(r + 1);XCC.push_back(xc);}}compress<int> XCCcomp(XCC);int M = XCCcomp.size();vector<compress<int>> comp(M, compress<int>(vector<int>(0)));vector<BinaryIndexedTree<int>> BIT(M, BinaryIndexedTree<int>(0));for(auto [k, x] : time){int idx = XCCcomp.get(k);comp[idx] = compress<int>(x);BIT[idx] = BinaryIndexedTree<int>(comp[idx].size());}for(int i = 0; i < N; i++){BIT[0].add(comp[0].get(L[i]), 1);BIT[0].add(comp[0].get(R[i] + 1), -1);int idx = XCCcomp.get(XC[i]);BIT[idx].add(comp[idx].get(L[i]), 1);BIT[idx].add(comp[idx].get(R[i] + 1), -1);}for(int i = 0; i < Q; i++){auto [type, a, b, c] = query[i];if(type == 1){int idx = XCCcomp.get(a);if(BIT[idx].sum(0, comp[idx].get(b) + 1) == 1){cout << "Yes" << endl;}else{cout << "No" << endl;}}else if(type == 2){cout << BIT[0].sum(0, comp[0].get(a) + 1) << endl;}else{int idx = XCCcomp.get(a);BIT[0].add(comp[0].get(b), 1);BIT[0].add(comp[0].get(c + 1), -1);BIT[idx].add(comp[idx].get(b), 1);BIT[idx].add(comp[idx].get(c + 1), -1);}}}