oj.uz

Submission #381657

# Submission time Handle Problem Language Result Execution time Memory
381657 2021-03-25T13:13:34 Z sad Sails (IOI07_sails) C++14
100 / 100
 284 ms 4068 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 14 ms 2412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1132 KB Output is correct
2 Correct 60 ms 1132 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1892 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 3296 KB Output is correct
2 Correct 196 ms 4068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 3260 KB Output is correct
2 Correct 145 ms 3952 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 3452 KB Output is correct
2 Correct 184 ms 2784 KB Output is correct