Submission #1084577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084577		BLOBVISGOD	Sails (IOI07_sails)	C++17	100 / 100	39 ms	2652 KiB

sails

#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 / 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