Submission #332906

#	Time	Username	Problem	Language	Result	Execution time	Memory
332906		vkgainz	Sails (IOI07_sails)	C++17	90 / 100	1073 ms	4824 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//nlog^2n should work...?
const int MX = 1e5+20;
int seg[4*MX], lazy[4*MX];
int sz = 1;
void prop(int x, int lx, int rx) {
    seg[x]+=lazy[x];
    if(rx-lx!=1) {
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
    }
    lazy[x] = 0;
}
int numLess(int l, int r, int c, int x=0, int lx=0, int rx=sz) { //gets color with <= appear <=k times
    prop(x, lx, rx);
    if(lx>=r || rx<=l) 
        return 0;
    int m = (lx+rx)/2;
    if(lx>=l && rx<=r) {
        if(seg[x]<=c) 
            return rx-lx;
        else {
            if(rx-lx==1)
                return 0;
            prop(2*x+1, lx, m), prop(2*x+2, m, rx);
            if(seg[2*x+2]<=c)
                return rx-m+numLess(l, r, c, 2*x+1, lx, m);
            else
                return numLess(l, r, c, 2*x+2, m, rx);
        }
    }
    return numLess(l, r, c, 2*x+1, lx, m)+numLess(l, r, c, 2*x+2, m, rx);
}
void upd(int l, int r, int x=0, int lx=0, int rx=sz) { //add 1 to [l, r)
    prop(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r) {
        ++seg[x];
        if(rx-lx!=1) {
            lazy[2*x+1]++;
            lazy[2*x+2]++;
        }
        return;
    }
    int m = (lx+rx)/2;
    upd(l, r, 2*x+1, lx, m), upd(l, r, 2*x+2, m, rx);
    seg[x] = max(seg[2*x+1], seg[2*x+2]);
}
vector<int> ret;
void push(int x=0, int lx=0, int rx=sz) {
    prop(x, lx, rx);
    if(rx-lx==1) {
        ret.push_back(seg[x]);
        return;
    }
    int m = (lx+rx)/2;
    push(2*x+1, lx, m);
    push(2*x+2, m, rx);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    while(sz<100005) sz*=2;
    vector<pair<int, int>> mast(n);
    for(int i=0;i<n;i++)
        cin >> mast[i].f >> mast[i].s;
    sort(mast.begin(), mast.end());
    for(int i=0;i<n;i++) {
        int h = mast[i].f;
        int k = mast[i].s;
        int lo = 0, hi = 100001;
        for(int j=0;j<20;j++) {
            int mid = (lo+hi)/2;
            if(numLess(0, h, mid)>k) {
                hi = mid;
            }
            else {
                lo = mid+1;
            }
        }
        int numIn = numLess(0, h, hi-1);
        upd(h-numIn, h);
        int numLeft = k-numIn;
        int start = h-numLess(0, h, hi);
        upd(start, start+numLeft);
    }
    push();
    long long ans = 0LL;
    //check for overflow
    for(int i=0;i<=100000;i++) {
        ans+=ret[i]*1LL*(ret[i]-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: 0 / 10