제출 #1332282

#제출 시각아이디문제언어결과실행 시간메모리
1332282user736482Bitaro the Brave 2 (JOI25_ho_t2)C++20
0 / 100
82 ms17464 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pii>
#define ff first
#define ss second
#define al(x) x.begin(),x.end() 
#define POT (1LL<<21)
#define rev(x) reverse(al(x))
#define ppi pair<pii,ll>
ll ns[300007];
ll sg[POT];
void dod(ll v,ll x){
    v+=POT/2-1;
    while(v){
        sg[v]+=x;v/=2;
    }
}
ll sm(ll v,ll l,ll r,ll pocz,ll kon){
    if(l>kon || r<pocz)return 0;
    if(l>=pocz && r<=kon)return sg[v];
    return sm(v*2,l,(l+r)/2,pocz,kon)+sm(v*2+1,(l+r)/2+1,r,pocz,kon);
}
int main(){ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,q,a,b,c;
    vector<ppi>v;
    vector<ppi>zap;
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>a>>b>>c;
        v.pb({{b,a},c});
        dod(a,c);
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        zap.pb({{a,b},i});
    }
    sort(al(v));sort(al(zap));
    rev(v);
    for(ppi i : zap){
        while(v.size() && v.back().ff.ff<i.ff.ff){
            //cout<<v.back().ff.ff<<" "<<v.back().ff.ss<< " ";
            dod(v.back().ff.ss,-v.back().ss);v.pop_back();
        }
        //cout<<"  "<<i.ff.ff<<" "<<i.ff.ss<<"\n";
        ns[i.ss]=sm(1,1,POT/2,1,i.ff.ss);
    }
    for(ll i=0;i<q;i++)cout<<ns[i]<<"\n";

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...