oj.uz

Submission #521585

# Submission time Handle Problem Language Result Execution time Memory
521585 2022-02-02T13:41:20 Z andrei_boaca Sails (IOI07_sails) C++17
100 / 100
 127 ms 3720 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
ll aib[100005];
ll lg;
struct date
{
    ll h,k;
} v[100005];
bool comp(date a, date b)
{
    return a.h<b.h;
}
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=lg;i+=lsb(i))
        aib[i]+=val;
}
ll query(int poz)
{
    ll rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].h>>v[i].k;
    sort(v+1,v+n+1,comp);
    lg=v[n].h;
    for(int i=1;i<=n;i++)
    {
        ll k=v[i].k;
        ll h=v[i].h;
        ll nr=query(h-k+1);
        ll first=h+1;
        ll st=1;
        ll dr=h;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(query(mij)<nr)
            {
                first=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        if(first<=h)
        {
            update(first,+1);
            update(h+1,-1);
        }
        ll lft=k-(h-first+1);
        st=1;
        dr=h;
        first=h;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(query(mij)<=nr)
            {
                first=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        update(first,+1);
        update(first+lft,-1);
    }
    ll ans=0;
    for(int i=1;i<=lg;i++)
    {
        ll val=query(i);
        ans+=val*(val-1)/2;
    }
    cout<<ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 300 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 612 KB Output is correct
2 Correct 26 ms 1048 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2056 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3080 KB Output is correct
2 Correct 94 ms 3124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3448 KB Output is correct
2 Correct 89 ms 3020 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3720 KB Output is correct
2 Correct 85 ms 3124 KB Output is correct