oj.uz

Submission #855486

# Submission time Handle Problem Language Result Execution time Memory
855486 2023-10-01T10:25:17 Z AndiR Sails (IOI07_sails) C++14
100 / 100
 74 ms 3820 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

ll n, aib[Nmax];

void aib_add(ll l, ll r, ll val){
    while (l<Nmax){
        aib[l]+=val;
        l+=l&-l;
    }
    r++;
    while (r<Nmax){
        aib[r]-=val;
        r+=r&-r;
    }
}
ll aib_val(ll pos){
    ll s=0;
    while (pos>0){
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}
ll aib_bs2(ll val, ll h){
    ll l=1, r=h, mij, v, sol=0;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v>=val){
            sol=mij;
            l=mij+1;
        }
        else r=mij-1;
    }
    return sol;
}
ll aib_bs1(ll val, ll h){
    ll l=1, r=h, mij, v, sol=0;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v<=val){
            sol=mij;
            r=mij-1;
        }
        else l=mij+1;
    }
    return sol;
}

struct mat{
    ll h, k;
}v[Nmax];

bool cmp(mat a, mat b){
    return a.h<b.h;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (ll i=0; i<n; i++)
        cin>>v[i].h>>v[i].k;
    sort(v, v+n, cmp);
    for (ll i=0; i<n; i++){
        ll val=aib_val(v[i].h-v[i].k+1);
        ll l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
        ll st=v[i].k-(v[i].h-r+1);

        aib_add(r, v[i].h, 1);
        aib_add(l, l+st-1, 1);
    }
    ll sol=0;
    for (ll i=1; i<Nmax; i++){
        sol+=aib_val(i)*(aib_val(i)-1)/2;
    }
    cout<<sol;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 348 KB Output is correct
2 Correct 2 ms 348 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 1 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 16 ms 2780 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3108 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3644 KB Output is correct
2 Correct 50 ms 3668 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3676 KB Output is correct
2 Correct 48 ms 3412 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3820 KB Output is correct
2 Correct 45 ms 3676 KB Output is correct