結果

問題 No.2421 entersys?
ユーザー through
提出日時 2023-08-12 15:04:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 794 ms / 3,000 ms
コード長 3,521 bytes
コンパイル時間 4,592 ms
コンパイル使用メモリ 284,516 KB
最終ジャッジ日時 2025-02-16 05:40:31
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using T = tuple<ll, string, ll, ll, ll>;
#include <atcoder/all>
using namespace atcoder;
// using mint = modint1000000007;
#define rep(i, n) for(ll i = 0; i < n; i++)
// S data, F lazy
using S = ll;
using F = ll;
// operator()
S op(S a,S b){
return a+b;
}
//
S mapping(F f,S x){
return f+x;
}
//
F composition(F f,F g){
return f+g;
}
S e(){ return 0; } // (op(e, a) = op(a, e) = a)
F id(){ return 0; } // mapping(id, a) = a
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll n; cin >> n;
vector<ll> comp;
map<string,set<ll>> nyu, tai;
vector<P> kukan;
rep(i,n) {
string x; ll l,r; cin >> x >> l >> r;
nyu[x].insert(l);
tai[x].insert(r);
comp.push_back(l);
comp.push_back(r);
kukan.push_back(P(l,r));
}
ll q; cin >> q;
vector<T> query(q);
rep(i,q) {
ll qq; cin >> qq;
if( qq == 1 ) {
string x; ll t; cin >> x >> t;
query[i] = T(qq,x,-1,-1,t);
comp.push_back(t);
}
else if( qq == 2 ) {
ll t; cin >> t;
query[i] = T(qq,"",-1,-1,t);
comp.push_back(t);
}
else {
string x; ll l,r; cin >> x >> l >> r;
query[i] = T(qq,x,l,r,-1);
comp.push_back(l);
comp.push_back(r);
}
}
sort(comp.begin(),comp.end());
comp.erase( unique(comp.begin(),comp.end()), comp.end() );
lazy_segtree<S,op,e,F,mapping,composition,id> lsg(comp.size());
rep(i,kukan.size()) {
auto &&[l,r] = kukan[i];
ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
lsg.apply(i1,i2+1,1);
}
rep(i,q) {
auto &&[qq,x,l,r,t] = query[i];
if( qq == 1 ) {
auto itr1 = nyu[x].upper_bound(t);
if( itr1 == nyu[x].begin() ) {
cout << "No" << endl;
continue;
}
itr1--;
auto itr2 = tai[x].upper_bound(*itr1);
if( itr2 == tai[x].end() || *itr2 < t ) cout << "No" << endl;
else cout << "Yes" << endl;
}
else if( qq == 2 ) {
ll i = lower_bound(comp.begin(), comp.end(), t) - comp.begin();
// cout << i << " " << comp.size() << endl << flush;
cout << lsg.get(i) << endl;
}
else {
// cout << "Yeah!" << endl << flush;
ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
// cout << i1 << " " << i2 << endl << flush;
lsg.apply(i1,i2+1,1);
if( tai[x].count(l) && nyu[x].count(r) ) {
tai[x].erase(tai[x].find(l));
nyu[x].erase(nyu[x].find(r));
}
else if( tai[x].count(l) && !nyu[x].count(r) ) {
tai[x].erase(tai[x].find(l));
tai[x].insert(r);
}
else if( !tai[x].count(l) && nyu[x].count(r) ) {
nyu[x].erase(tai[x].find(r));
nyu[x].insert(l);
}
else {
nyu[x].insert(l);
tai[x].insert(r);
}
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0