結果
| 問題 | No.2421 entersys? |
| ユーザー |
 Ping Chung Chang
|
| 提出日時 | 2023-09-01 16:52:42 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,876 bytes |
| コンパイル時間 | 3,193 ms |
| コンパイル使用メモリ | 184,284 KB |
| 実行使用メモリ | 472,320 KB |
| 最終ジャッジ日時 | 2024-06-11 02:35:32 |
| 合計ジャッジ時間 | 14,963 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 296 ms
472,192 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | TLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
struct node{
int pl,pr;
ll val = 0,tag = 0;
ll l,r;
node(){
pl = pr = 0;
tag = val = 0;
l = r = 0;
}
node(ll s,ll e){
l = s,r = e;
tag = val = 0;
pl = pr = 0;
}
};
const int mxn = 2e5+10;
const int inf = 1e9+10;
node segtree[mxn*60];
int ppp = 0;
int newnode(int l,int r){
ppp++;
segtree[ppp] = node(l,r);
return ppp;
}
void modify(int now,int s,int e,int v){
if(segtree[now].l>=s&&segtree[now].r<=e){
segtree[now].tag += v;
return;
}
int mid = (segtree[now].l+segtree[now].r)>>1;
segtree[now].val = 0;
if(mid>=s){
if(!segtree[now].pl)segtree[now].pl = newnode(segtree[now].l,mid);
modify(segtree[now].pl,s,e,v);
}
if(mid<e){
if(!segtree[now].pr)segtree[now].pr = newnode(mid+1,segtree[now].r);
modify(segtree[now].pr,s,e,v);
}
if(segtree[now].pl)
segtree[now].val += segtree[segtree[now].pl].tag*(mid-segtree[now].l+1)+segtree[segtree[now].pl].val;
if(segtree[now].pr)
segtree[now].val += segtree[segtree[now].pr].tag*(segtree[now].r-mid)+segtree[segtree[now].pr].val;
return;
}
ll getval(int now,int s,int e){
if(!now)return 0LL;
if(segtree[now].l>=s&&segtree[now].r<=e){
return segtree[now].val+segtree[now].tag*(min(1LL*e,segtree[now].r)-max(1LL*s,segtree[now].l)+1);
}
int mid = (segtree[now].l+segtree[now].r)>>1;
ll re = segtree[now].tag*(min(1LL*e,segtree[now].r)-max(1LL*s,segtree[now].l)+1);
if(segtree[now].pl&&s<=mid)re += getval(segtree[now].pl,s,e);
if(segtree[now].pr&&mid<e)re += getval(segtree[now].pr,s,e);
return re;
}
vector<string> all;
vector<int> head;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
tuple<string,int,int> arr[n];
for(auto &i:arr)cin>>get<0>(i)>>get<1>(i)>>get<2>(i),all.push_back(get<0>(i));
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i = 0;i<=all.size();i++){
head.push_back(newnode(0,inf));
}
for(auto &i:arr){
int pos = lower_bound(all.begin(),all.end(),get<0>(i))-all.begin();
modify(head[pos],get<1>(i),get<2>(i),1);
modify(head[all.size()],get<1>(i),get<2>(i),1);
}
int Q;
cin>>Q;
while(Q--){
int t;
cin>>t;
if(t == 1){
string s;
int t;
cin>>s>>t;
auto pos = lower_bound(all.begin(),all.end(),s)-all.begin();
ll val = getval(head[pos],t,t);
if(val)cout<<"Yes\n";
else cout<<"No\n";
}
else if(t == 2){
int t;
cin>>t;
cout<<getval(head[all.size()],t,t)<<'\n';
}
else{
string s;
int l,r;
cin>>s>>l>>r;
int pos = lower_bound(all.begin(),all.end(),s)-all.begin();
modify(head[pos],l,r,1);
modify(head[all.size()],l,r,1);
}
}
return 0;
}