oj.uz

Submission #751366

# Submission time Handle Problem Language Result Execution time Memory
751366 2023-05-31T12:36:18 Z amin Sails (IOI07_sails) C++14
100 / 100
 554 ms 6316 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int seg[4000000];
int laz[4000000];
int a[4000003];
int z;
int b[4000003];
int ans=0;
int n;
void merg(int v,int v1,int v2)
{

  seg[v]=max(seg[v1],seg[v2]);


}
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        seg[v]=a[tl];
        return ;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    merg(v,v*2,v*2+1);
}

void push(int v)
{
    laz[v*2]+=laz[v];
    seg[v*2]+=laz[v];
    seg[v*2+1]+=laz[v];
    laz[v*2+1]+=laz[v];
    laz[v]=0;
}
void update(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return ;
    if(tl==l&&tr==r)
    {
      seg[v]++;
      laz[v]++;

        return ;

    }
    push(v);
    int tm=(tl+tr)>>1;
   update(v*2,tl,tm,l,min(r,tm));
   update(v*2+1,tm+1,tr,max(tm+1,l),r);
    merg(v,v*2,v*2+1);

}

int get1(int v,int tl,int tr,int pos)
{
  //  cout<<tl<<' '<<tr<<' '<<pos<<endl;
    if(pos<tl||pos>tr)
        return 1500000000;
    if(tl==tr)
        return seg[v];
    int tm=(tl+tr)>>1;
    push(v);
    return min(get1(v*2,tl,tm,pos),get1(v*2+1,tm+1,tr,pos));

}
int get(int v,int l,int r,int val)
{
    //cout<<tl<<' '<<tr<<endl;
   /* if(val<tl||val>tr)
        return 1000000;*/
     //   cout<<tl<<' '<<tr<<endl;
    l--;

     while(l+1<r)
     {int m=(l+r)/2;
     if(get1(1,0,150000,m)<val)
        l=m;
     else
        r=m;
     }
     if(get1(1,0,150000,150000)<val)
        return 150001;
     else
        return r;


}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //  freopen("balancing.in","r",stdin);
   // freopen("balancing.out","w",stdout);

cin>>n;
int q;
pair<int,int>h[n];
for(int i=0;i<n;i++)
{
    cin>>h[i].first>>h[i].second;
}
sort(h,h+n);
for(int i=0;i<n;i++)
{
    int height=h[i].first;
    int number=h[i].second;
    int st=150000-height+1;
    int en=st+number-1;
    int valen=get1(1,0,150000,en);
    int nos=get(1,st,150000,valen);
    int noe=get(1,st,150000,valen+1);
   // cout<<valen<<' '<<nos<<' '<<noe<<endl;
    update(1,0,150000,st,nos-1);
int left=number-(nos-st);
update(1,0,150000,noe-left,noe-1);
/*for(int y=st;y<=150000;y++)
{
    cout<<get1(1,0,150000,y)<<' ';
}
cout<<endl;*/
}
    ll ans=0;
    for(int i=0;i<=150000;i++)
    {
        ll p=get1(1,0,150000,i);
        if(p>0)
           // cout<<p<<endl;
        ans+=(p)*(p-1)/2;
    }

    cout<<ans<<endl;


}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:105:5: warning: unused variable 'q' [-Wunused-variable]
  105 | int q;
      |     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4424 KB Output is correct
2 Correct 22 ms 4428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4408 KB Output is correct
2 Correct 17 ms 4436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4344 KB Output is correct
2 Correct 33 ms 4364 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4360 KB Output is correct
2 Correct 20 ms 4320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4432 KB Output is correct
2 Correct 44 ms 4408 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4476 KB Output is correct
2 Correct 143 ms 4932 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 4972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 5452 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 5932 KB Output is correct
2 Correct 444 ms 5852 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 6096 KB Output is correct
2 Correct 404 ms 5752 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 6316 KB Output is correct
2 Correct 414 ms 6256 KB Output is correct