Submission #381657

#	Time	Username	Problem	Language	Result	Execution time	Memory
381657		sad	Sails (IOI07_sails)	C++14	100 / 100	284 ms	4068 KiB

sails

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
using namespace std;
int n;const int N=400090;
int mx[N],laz[N];
void plaz(int ind,int l)
{
    mx[ind]+=laz[ind];
    if(l>1)
    {
        laz[ind*2+1]+=laz[ind];
        laz[ind*2+2]+=laz[ind];
    }
    laz[ind]=0;
}
void up(int ind,int st,int end,int l,int r,int x)
{
    if(r<l)return;
    plaz(ind,end-st+1);
    if(l>end||r<st)return;
    if(l<=st&&end<=r)
    {
        laz[ind]+=x;
        plaz(ind,end-st+1);
        return;
    }
    int m=(st+end)/2;
    up(ind*2+1,st,m,l,r,x);
    up(ind*2+2,m+1,end,l,r,x);
    mx[ind]=max(mx[ind*2+1],mx[ind*2+2]);
}
int get(int ind,int st,int end,int u)
{
    plaz(ind,end-st+1);
    if(st==end)
    {
        return mx[ind];
    }
    int m=(st+end)/2;
    if(u>m)return get(ind*2+2,m+1,end,u);
    else return get(ind*2+1,st,m,u);
}
int  go2(int ind,int st,int end,int x)
{
    plaz(ind,end-st+1);
    if(st==end)
        return st;
    int m=(st+end)/2;
    plaz(ind*2+1,m-st+1);
    plaz(ind*2+2,end-m);
    if(mx[ind*2+1]<=x)return go2(ind*2+2,m+1,end,x);
    return go2(ind*2+1,st,m,x);
}
int go1(int ind,int st,int end,int x)
{
    plaz(ind,end-st+1);
    if(st==end)
        return st;
    int m=(st+end)/2;
    plaz(ind*2+1,m-st+1);
    plaz(ind*2+2,end-m);
    if(mx[ind*2+1]<x)return go1(ind*2+2,m+1,end,x);
    return go1(ind*2+1,st,m,x);
}int m;
pair<int,int>go(int x)
{
    int l=go1(0,0,m,x);
    int r=go2(0,0,m,x)-1;
    return {l,r};
}
vector<pair<int,int> >v;
int main()
{
    cin>>n;m=0;
    for(int i=0;i<n;i++)
    {
        int h,k;cin>>h>>k;
        v.pb({h,k});m=max(m,h);
    }m++;
    up(0,0,m,m,m,1e9);
    sort(v.begin(),v.end());
    int last=0;///memset
    int r=m,l=m;
    for(auto it:v)
    {
        int k=it.se;
        l-=(it.fi-last);
        int x=get(0,0,m,l+k-1);
        pair<int,int>t=go(x);
        t.fi=max(l,t.fi);
        up(0,0,m,l,t.fi-1,1);//cout<<t.fi<<" "<<t.se<<"   ";
        int w=max(t.fi-l,0);
        w=k-w;//cout<<t.se-w+1<<" "<<t.se<<endl;
        up(0,0,m,t.se-w+1,t.se,1);last=it.fi;
    }
    ll re=0;
    for(int i=1;i<=m-1;i++)
        {
            ll x=get(0,0,m,i);
            x*=(x-1);x/=2;
            re+=x;
        }
        cout<<re;

}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:86:9: warning: unused variable 'r' [-Wunused-variable]
   86 |     int r=m,l=m;
      |         ^

• 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