제출 #1352791

#제출 시각아이디문제언어결과실행 시간메모리
1352791WarinchaiSails (IOI07_sails)C++20
0 / 100
55 ms7788 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int h[100005];
int k[100005];
int n;

struct segtree{
    int info[400005];
    int lz[400005];
    void apply(int st,int en,int i,int val){
        info[i]+=val;
        lz[i]+=val;
    }
    void push(int st,int en,int i){
        int m=(st+en)/2;
        apply(st,m,i*2,lz[i]);
        apply(m+1,en,i*2+1,lz[i]);
        lz[i]=0;
    }
    void upd(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l)return;
        if(st>=l&&en<=r)return apply(st,en,i,val);
        push(st,en,i);
        int m=(st+en)/2;
        upd(st,m,i*2,l,r,val);
        upd(m+1,en,i*2+1,l,r,val);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    int fans(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        push(st,en,i);
        int m=(st+en)/2;
        return max(fans(st,m,i*2,l,r),fans(m+1,en,i*2+1,l,r));
    }
    int f(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l||info[i]<val)return 0;
        if(st==en)return st;
        push(st,en,i);
        int m=(st+en)/2;
        auto x=f(m+1,en,i*2+1,l,r,val);
        if(x!=0)return x;
        return f(st,m,i*2,l,r,val);
    }
}tr;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cerr<<"work\n";
    cin>>n;
    int left=0;
    int mx=0;
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>k[i];
        v.push_back({h[i],k[i]});
        mx=max(mx,h[i]);
    }
    sort(v.begin(),v.end());
    for(auto [h,k]:v){
        int x=tr.fans(1,mx,1,h-k+1,h-k+1);
        int pos=tr.f(1,mx,1,1,h,x+1)+1;
        tr.upd(1,n,1,pos,pos+k-1,1);
        //cerr<<"h,k:"<<h<<' '<<k<<"\n";
        //cerr<<"upd:"<<pos<<" "<<pos+k-1<<"\n";
        //for(int i=1;i<=mx;i++)cerr<<tr.fans(1,n,1,i,i)<<' ';
        //cerr<<"\n";
    }
    int ans=0;
    for(int i=1;i<=mx;i++){
        int val=tr.fans(1,n,1,i,i);
        //cerr<<"i:"<<i<<" "<<val<<"\n";
        ans+=val*(val-1)/2;
    }
    cout<<ans;
}
#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...
#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...