제출 #1237249

#제출 시각아이디문제언어결과실행 시간메모리
1237249denislavSails (IOI07_sails)C++20
0 / 100
97 ms5196 KiB
# include <iostream>
# include <algorithm>
using namespace std;

const int MAX=1e5+11;

int n,m=1e5;
pair<int,int> a[MAX];

long long tree[MAX*4];
long long lazy[MAX*4];

void push_lazy(int v, int l, int r)
{
    if(lazy[v]==0) return ;

    tree[v]+=lazy[v]*(r-l+1);
    if(l!=r)
    {
        lazy[v*2]+=lazy[v];
        lazy[v*2+1]+=lazy[v];
    }
    lazy[v]=0;
}

void update(int le, int ri, int d, int v=1, int l=1, int r=m)
{
    push_lazy(v,l,r);
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        lazy[v]+=d;
        push_lazy(v,l,r);
        return ;
    }

    int mid=(l+r)/2;
    update(le,ri,d,v*2,l,mid);
    update(le,ri,d,v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}

long long query(int le, int ri, int v=1, int l=1, int r=m)
{
    push_lazy(v,l,r);
    if(ri<l or r<le) return 0;
    if(le<=l and r<=ri) return tree[v];

    int mid=(l+r)/2;
    return query(le,ri,v*2,l,mid)+query(le,ri,v*2+1,mid+1,r);
}

long long ans=0;

void perform(int l, int r)
{
    ans+=query(l,r);
    update(l,r,1);

    //cout<<"->"<<l<<" "<<r<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);

    int last=1;
    for(int i=1;i<=n;i++)
    {
        int all=a[i].first,left=a[i].second;
        if(last+left-1>=all)
        {
            perform(last,all);
            left-=(all-last+1);
            last=1;
        }
        if(left>0)
        {
            perform(last,last+left-1);
            last=last+left;
        }
    }

    cout<<ans<<"\n";

    return 0;
}



#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...