Submission #1278630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278630		lambd47	Sails (IOI07_sails)	C++20	0 / 100	102 ms	3576 KiB

sails

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mh=1e5+7;
void solve() {
    int n;cin>>n;
    vector<int> h(n);
    vector<int> vec(n);
    vector<int> ord(n);
    iota(all(ord),0);
    L(i,0,n-1)cin>>h[i]>>vec[i];
    sort(all(ord),[&](int i, int j){
           return h[i]>h[j]; 
    });




    vector<int> bt(mh);
    auto upd=[&](int i,int v){
        while(i<mh){
            bt[i]+=v;
            i+=(i&(-i));
        }
    };
    auto updi=[&](int i, int j){
        upd(i,1);
        upd(j+1,-1);
    };
    auto qry=[&](int i)->int{
        if(i==0)return 0;
        int ret=0;
        while(i>0){
            ret+=bt[i];
            i-=(i&(-i));
        }
        return ret;
    };

    auto testa=[&](int mx)->int{
        fill(all(bt),0);
        int at=h[ord[0]];
        int resp=0;
        for(auto id:ord){
            while(at>h[id]){
                int x=qry(at);
                resp+=(x*(x-1))/2;
                at--;
            }
            while((qry(at))==mx){
                resp+=(mx*(mx-1))/2;
                at--;
            }
            if(at<vec[id])return -1;
            updi(at-vec[id]+1,at);
           
        }
        while(at>0){
            int x=qry(at);
            resp+=(x*(x-1))/2;
            at--;
        }
        return resp;
    };

    int l=1;
    int r=n;
    int resp=0;
    while(l<=r){
        int m=(l+r)/2;
        int at=testa(m);
        if(at==-1){
            l=m+1;
        }
        else{
            resp=at;
            r=m-1;
        }
    }
    cout<<resp<<"\n";





}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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