Submission #957839

#	Time	Username	Problem	Language	Result	Execution time	Memory
957839		ASN49K	Sails (IOI07_sails)	C++14	100 / 100	71 ms	2600 KiB

sails

#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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10