oj.uz

Submission #1084577

# Submission time Handle Problem Language Result Execution time Memory
1084577 2024-09-06T12:13:52 Z BLOBVISGOD Sails (IOI07_sails) C++17
100 / 100
 39 ms 2652 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct fentree{
    vi a;
    fentree(int N) : a(N+1) {}

    void add(int at, int v){
        for(at++; at<sz(a); at+=at&(-at)) a[at] += v;
    }void rangeadd(int l, int r, int v){
        add(l,v);
        add(r,-v);
    }int get(int at){
        int ans = 0;
        for(at++; at>0; at-=at&(-at)) ans += a[at];
        return ans;
    }int lowerbound(int v){
        int sm = 0, at = 0;
        for(int pw = 1<<__lg(sz(a)-1); pw>0; pw/=2){
            if (at+pw < sz(a) and sm + a[at+pw] > v){
                at+=pw;
                sm += a[at];
            }
        }return at;
    }
};

const int N = 1e5+10;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n; cin >> n;

    vector<array<int,2>> a(n);
    rep(i,0,n) rep(j,0,2) cin >> a[i][j];
    sort(all(a));

    fentree fen(N);
    auto update = [&](int cnt, int r) -> void {
        int col = fen.get(r-cnt); // smallest col
        int L2 = fen.lowerbound(col-1);
        int L1 = fen.lowerbound(col);
        if (L2 >= r){
            fen.rangeadd(L1,L1+cnt,1);
        }else{
            int numleft = L2 - (r-cnt);
            fen.rangeadd(L1,L1+numleft,1);
            fen.rangeadd(L2,r,1);
        }
    };

    for(auto [h,c] : a) update(c,h);
    ll ans = 0;
    rep(i,0,N) {
        ll x = fen.get(i);
        ans += (x*(x-1))/2;
    }

    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 11 ms 1256 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2256 KB Output is correct
2 Correct 26 ms 2136 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2580 KB Output is correct
2 Correct 31 ms 2136 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2652 KB Output is correct
2 Correct 27 ms 2652 KB Output is correct