Submission #1237249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237249		denislav	Sails (IOI07_sails)	C++20	0 / 100	97 ms	5196 KiB

sails

# 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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10