oj.uz

Submission #861682

# Submission time Handle Problem Language Result Execution time Memory
861682 2023-10-16T16:21:06 Z HuyQuang_re_Zero Sails (IOI07_sails) C++14
100 / 100
 116 ms 7256 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4568 KB Output is correct
2 Correct 7 ms 4712 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 7 ms 4560 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4716 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4700 KB Output is correct
2 Correct 8 ms 4564 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4612 KB Output is correct
2 Correct 9 ms 4776 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4936 KB Output is correct
2 Correct 37 ms 5300 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5804 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6772 KB Output is correct
2 Correct 76 ms 6812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 7160 KB Output is correct
2 Correct 62 ms 6776 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7256 KB Output is correct
2 Correct 84 ms 7188 KB Output is correct