Submission #1357968

#TimeUsernameProblemLanguageResultExecution timeMemory
1357968AMel0nSails (IOI07_sails)C++20
100 / 100
125 ms11372 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAXH = 1e5;

/*
Iterate thru masts in increasing order of height
Have an array where V[i] = number of sails at level (height) i
At each mast, we pick the K least frequent levels
Maintain the array so that each level has more or same amount of sails than the next
If H-K+1 belongs to an interval where all the values are equal:
  let [A, B] be that interval
  increase [A, A + B - (H-K+1)] and [B+1, H]
  to maintain the non increasing order
Else increase to the range [H-K+1, H]
  we can actually omit this if we consider H-K+1 in an interval of size 1

Segtree levels 0 indexed
*/

int N;
vector<pair<int,int>> cnt, tree;
vector<int> lazy;

void push(int tl, int tr, int i) {
    if (lazy[i]) {
        tree[i].first += lazy[i];
        tree[i].second += lazy[i];
        if (tl != tr) {
            lazy[i * 2] += lazy[i];
            lazy[i * 2 + 1] += lazy[i];
        }
        lazy[i] = 0;
    }
}
void update(int l, int r, int tl = 0, int tr = MAXH-1, int i = 1) {
    push(tl, tr, i);
    if (l > r) return ;
    if (tl == l && tr == r) {
        lazy[i]++;
        push(tl, tr, i);
        return ;
    }
    int tm = (tl + tr) / 2;
    update(l, min(r, tm), tl, tm, i * 2);
    update(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
    tree[i].first = min(tree[i * 2].first, tree[i * 2 + 1].first);
    tree[i].second = max(tree[i * 2].second, tree[i * 2 + 1].second);
}
int lb(int v, int tl = 0, int tr = MAXH-1, int i = 1) {
    push(tl, tr, i);
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    push(tl, tm, i * 2), push(tm + 1, tr, i * 2 + 1);
    if (tree[i * 2].first <= v) return lb(v, tl, tm, i * 2);
    return lb(v, tm + 1, tr, i * 2 + 1);
}
int rb(int v, int tl = 0, int tr = MAXH-1, int i = 1) {
    push(tl, tr, i);
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    push(tl, tm, i * 2), push(tm + 1, tr, i * 2 + 1);
    if (tree[i * 2 + 1].second >= v) return rb(v, tm + 1, tr, i * 2 + 1);
    return rb(v, tl, tm, i * 2);
}
int query(int p, int tl = 0, int tr = MAXH-1, int i = 1) {
    while(tl != tr) {
        int tm = (tl + tr) / 2;
        push(tl, tr, i);
        if (p <= tm) {tr = tm; i = i * 2;}
        else {tl = tm + 1; i = i * 2 + 1;}
    }
    push(tl, tr, i);
    return tree[i].first;
}

signed main() {
    cin >> N;
    cnt.resize(N), tree.resize(MAXH*4), lazy.resize(MAXH*4);
    for(int i = 0; i < N; i++) {
        int h, k; cin >> h >> k;
        h--;
        cnt[i] = {h, k};
    }
    sort(cnt.begin(), cnt.end());

    for(auto &[h, k]: cnt) {
        int v = query(h-k+1);
        int a = lb(v), b = min(rb(v), h);
        update(a, a + b - (h-k+1));
        update(b+1, h);
    }
    int re = 0;
    for(int i = 0; i < MAXH; i++) {
        int x = query(i);
        re += (x-1)*x/2;
    }
    cout << re;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...