Submission #861682

#	Time	Username	Problem	Language	Result	Execution time	Memory
861682		HuyQuang_re_Zero	Sails (IOI07_sails)	C++14	100 / 100	116 ms	7256 KiB

sails

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
ll n,m,i,k,h,res;
II a[N];
struct Interval_Tree
{
    int lz[4*N];
    struct node { int l,r; } st[4*N];
    void modify(int id,int k) { lz[id]+=k; st[id].l+=k; st[id].r+=k; }
    void down(int id)
    {
        modify(id*2,lz[id]); modify(id*2+1,lz[id]);
        lz[id]=0;
    }
    void update(int id,int l,int r,int u,int v)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { modify(id,1); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v); update(id*2+1,mid+1,r,u,v);
        st[id].l=st[id*2].l;
        st[id].r=st[id*2+1].r;
    }
    int get(int id,int l,int r,int u)
    {
        if(l==r) return lz[id];
        down(id);
        int mid=(l+r)>>1;
        if(u<=mid) return get(id*2,l,mid,u);
        return get(id*2+1,mid+1,r,u);
    }
    int FindL(int id,int l,int r,int k)
    {
        if(l==r) return l;
        down(id);
        int mid=(l+r)>>1;
        if(st[id*2].r>=k) return FindL(id*2,l,mid,k);
        return FindL(id*2+1,mid+1,r,k);
    }
    int FindR(int id,int l,int r,int k)
    {
        if(l==r) return l;
        down(id);
        int mid=(l+r)>>1;
        if(st[id*2+1].l<=k) return FindR(id*2+1,mid+1,r,k);
        return FindR(id*2,l,mid,k);
    }
} IT;


int main()
{
  //  freopen("sails.inp","r",stdin);
    //freopen("sails.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i].fst>>a[i].snd;
    sort(a+1,a+n+1);
    m=100000;
    for(i=1;i<=n;i++)
    {
        int Begin=m-a[i].fst+1,u=Begin+a[i].snd-1,k=IT.get(1,1,m,u),
            l=max(Begin,IT.FindL(1,1,m,k)),r=IT.FindR(1,1,m,k);
        IT.update(1,1,m,Begin,l-1);
        IT.update(1,1,m,r-(u-l),r);
    }
    for(i=1;i<=m;i++)
    {
        k=IT.get(1,1,m,i);
        res+=k*(k-1)/2;
    }
    cout<<res;
}

• 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