Submission #114251

#	Time	Username	Problem	Language	Result	Execution time	Memory
114251		nvmdava	Sails (IOI07_sails)	C++17	30 / 100	1069 ms	4080 KiB

sails

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

#define N 131072
#define inf 250000
int seg[N << 1];
int cnt[N + 2];

vector<pii> fru;
vector<pii> upd;

void update(int x, int val){
    cnt[x] = val;
    x = x + N - 1;
    seg[x] = x - N + 1;
    x >>= 1;
    while(x){
        int l, r;
        l = seg[x << 1];
        r = seg[x << 1 | 1];
        if(cnt[l] > cnt[r])
            seg[x] = r;
        else
            seg[x] = l;
        x >>= 1;
    }
}

int query(int id, int l, int r, int L, int R){
    if(l >= L && R >= r) return seg[id];
    if(l > R || r < L) return 0;

    int m = (l + r) >> 1;
    int ll = query(id << 1, l, m, L, R);
    int rr = query(id << 1 | 1, m + 1, r, L, R);
    if(ll * rr == 0) return ll + rr;
    if(cnt[ll] > cnt[rr]) return rr;
    return ll;
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    for(int i = 1; i <= N; i++)
        update(i, 0);

    cin>>n;
    fru.resize(n);

    for(int i = 0; i < n; i++)
        cin>>fru[i].ff>>fru[i].ss;
//    cerr<<'\n';
    sort(fru.begin(), fru.end());

    for(auto s : fru){
//        cerr<<s.ff<<' '<<s.ss<<"\n";
        while(s.ss--){
            int x = query(1, 1, N, 1, s.ff);
//            cerr<<x<<' ';
            upd.push_back({x, cnt[x] + 1});
            update(x, inf);
        }
//        cerr<<'\n'<<'\n';
        while(!upd.empty()){
            update(upd.back().ff, upd.back().ss);
            upd.pop_back();
        }
    }

    long long res = 0;

    for(int i = 1; i < N; i++){
        res += 1LL * cnt[i] * (cnt[i] - 1) / 2;
    }
    cout<<res;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 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