oj.uz

Submission #817927

# Submission time Handle Problem Language Result Execution time Memory
817927 2023-08-09T20:30:10 Z serifefedartar Sails (IOI07_sails) C++17
100 / 100
 595 ms 4280 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 7
#define MAXN 100005

vector<pair<int,int>> mast;
int sg[4*MAXN], lazy[4*MAXN];
void update(int k, int a, int b, int q_l, int q_r) {
    if (lazy[k]) {
        sg[k] += (b-a+1) * lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }

    if (q_l > b || q_r < a)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] += b-a+1;
        if (a != b) {
            lazy[2*k]++;
            lazy[2*k+1]++;
        }
        return ;
    }
    update(2*k, a, (a+b)/2, q_l, q_r);
    update(2*k+1, (a+b)/2+1, b, q_l, q_r);
    sg[k] = sg[2*k] + sg[2*k+1];
}

int get(int k, int a, int b, int plc) {
    if (lazy[k]) {
        sg[k] += (b-a+1) * lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }

    if (plc < a || plc > b)
        return 0;
    if (a == b)
        return sg[k];
    return get(2*k, a, (a+b)/2, plc) + get(2*k+1, (a+b)/2+1, b, plc);
}

int main() {
    fast
    int N;
    cin >> N;

    mast = vector<pair<int,int>>(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, k = mast[i].s;
        int left = 100001 - h;
        int plc = get(1, 1, 100000, left + k - 1);

        int L = left, R = 100000;
        int ans = -1; 
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (get(1, 1, 100000, mid) < plc) {
                ans = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        L = left, R = 100000;
        int last_pos = -1;
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (get(1, 1, 100000, mid) <= plc) {
                last_pos = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        if (ans != -1) {
            update(1, 1, 100000, left, ans);
            k -= ans - left + 1;
        }

        if (k)
            update(1, 1, 100000, last_pos - k + 1, last_pos);
    }

    ll ans = 0;
    for (int i = 1; i <= 100000; i++) {
        ll q = get(1, 1, 100000, i);
        ans += q * (q-1) / 2;
    }
    cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB Output is correct
2 Correct 12 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 12 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 12 ms 380 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 332 KB Output is correct
2 Correct 14 ms 452 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 632 KB Output is correct
2 Correct 20 ms 2388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1100 KB Output is correct
2 Correct 115 ms 988 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 1588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 2336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 3896 KB Output is correct
2 Correct 383 ms 3836 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 4132 KB Output is correct
2 Correct 278 ms 3076 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 4280 KB Output is correct
2 Correct 358 ms 2836 KB Output is correct