oj.uz

Submission #957839

# Submission time Handle Problem Language Result Execution time Memory
957839 2024-04-04T11:39:30 Z ASN49K Sails (IOI07_sails) C++14
100 / 100
 71 ms 2600 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
using i64=long long;
const int mod=1e9+7;
const int inf=1e9;
int lg2(int x)
{
    return 31-__builtin_clz(x);
}
struct Aib
{
    int n;
    vector<int>aib;
    int lsb(int x)
    {
        return (x&(-x));
    }
    void update(int poz,int val)
    {
        for(;poz<=n;poz+=lsb(poz))
        {
            aib[poz]+=val;
        }
    }
    void update_range(int l,int r,int val)
    {
        update(l,val);
        update(r+1,-val);
    }
    int query(int poz)
    {
        int rez=0;
        for(;poz>0;poz-=lsb(poz))
        {
            rez+=aib[poz];
        }
        return rez;
    }
    int lower_bound(int search_val)
    {
        int lg=lg2(n);
        int rez=0;
        for(int i=(1<<lg);i>0;i>>=1)
        {
            if(rez+i<=n && aib[rez+i]<=search_val)
            {
                search_val-=aib[rez+i];
                rez+=i;
            }
        }
        return rez;
    }
    Aib(int n)
    {
        aib.assign(n+1,0);
        this->n=n;
    }
};

struct Duo
{
    int height,cnt;
};
main()
{
    int n;
    cin>>n;
    vector<Duo>a(n);

    for(auto &c:a)
    {
        cin>>c.height>>c.cnt;
    }
    sort(all(a) , [&](const Duo& a,const Duo& b){
         return a.height<b.height;
    });

    const int max_h=a[n-1].height;

    Aib aib(max_h);

    for(auto &c:a)
    {
        int pozl=max_h-c.height+1;

        int max_val_add=aib.query(pozl+c.cnt-1);
        int lb=max(aib.lower_bound(max_val_add-1),pozl-1);
        aib.update_range(pozl,lb,1);

        int ramas=c.cnt-(lb-pozl+1);
        lb=aib.lower_bound(max_val_add);
        aib.update_range(lb-ramas+1,lb,1);
    }

    i64 rez=0;
    for(int i=1;i<=max_h;i++)
    {
        int v=aib.query(i);
        rez+=1LL*v*(v-1)/2;
    }
    cout<<rez;
}

Compilation message

sails.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main()
      | ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 17 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2128 KB Output is correct
2 Correct 48 ms 2316 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2540 KB Output is correct
2 Correct 45 ms 2012 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2600 KB Output is correct
2 Correct 52 ms 2372 KB Output is correct