Submission #1237301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237301		denislav	Sails (IOI07_sails)	C++20	100 / 100	632 ms	7300 KiB

sails

# include <iostream>
# include <algorithm>
using namespace std;

const int MAX=1e5+11;

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

struct node
{
    long long sum;
    int mn,pos;

    node friend operator + (node A, node B)
    {
        node res;
        res.sum=A.sum+B.sum;
        if(A.mn<=B.mn)
        {
            res.mn=A.mn;
            res.pos=A.pos;
        }
        else
        {
            res.mn=B.mn;
            res.pos=B.pos;
        }

        return res;
    }
};

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

void build(int v=1, int l=1, int r=m)
{
    if(l==r)
    {
        tree[v]={0,0,l};
        return ;
    }

    int mid=(l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}

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

    tree[v].sum+=lazy[v]*(r-l+1);
    tree[v].mn+=lazy[v];
    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];
}

node 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,(int)1e9,(int)1e9};
    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).sum;
    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);

    build();
    for(int i=1;i<=n;i++)
    {
        int from=a[i].first,left=a[i].second;
        node nd=query(1,from-left+1);
        int pos=nd.pos;
        int l=pos,r=from,pos2=pos;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(query(pos,mid).pos==pos)
            {
                pos2=mid;
                l=mid+1;
            }
            else r=mid-1;
        }

        pos2++;
        //cout<<i<<":"<<pos<<" "<<pos2<<"\n";

        if(pos2<=from)
        {
            perform(pos2,from);
            left-=from-pos2+1;
        }
        if(left>0)
        {
            perform(pos,pos+left-1);
            left=0;
        }
    }

    cout<<ans<<"\n";

    return 0;
}

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