oj.uz

Submission #332906

# Submission time Handle Problem Language Result Execution time Memory
332906 2020-12-04T01:18:52 Z vkgainz Sails (IOI07_sails) C++17
90 / 100
 1000 ms 4824 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3000 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Correct 4 ms 3052 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3064 KB Output is correct
2 Correct 9 ms 3052 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3052 KB Output is correct
2 Correct 14 ms 3048 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3156 KB Output is correct
2 Correct 235 ms 3692 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 3584 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 4096 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 4588 KB Output is correct
2 Correct 980 ms 4588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 4824 KB Output is correct
2 Correct 741 ms 4460 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 3820 KB Time limit exceeded
2 Halted 0 ms 0 KB -