oj.uz

Submission #817672

# Submission time Handle Problem Language Result Execution time Memory
817672 2023-08-09T14:56:37 Z serifefedartar Sails (IOI07_sails) C++17
5 / 100
 578 ms 4288 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>> masts;
int sg[4*MAXN], lazy[4*MAXN];
void increment(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_r < a || q_l > b)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] += b-a+1;
        if (a != b) {
            lazy[2*k]++;
            lazy[2*k+1]++;
        }
        return ;
    }
    increment(2*k, a, (a+b)/2, q_l, q_r);
    increment(2*k+1, (a+b)/2+1, b, q_l, q_r);
    sg[k] = sg[2*k] + sg[2*k+1];
}

ll query(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 (b < plc || a > plc)
        return 0;
    if (a == b)
        return sg[k];
    return query(2*k, a, (a+b)/2, plc) + query(2*k+1, (a+b)/2+1, b, plc);
}

int main() {
    fast
    int N, H, K;
    cin >> N;

    masts = vector<pair<int,int>>(N);
    for (int i = 0; i < N; i++) {
        cin >> H >> K;
        masts[i] = {H, K};
    }
    sort(masts.begin(), masts.end());

    int left = 100001 - masts[0].f;
    for (int i = 0; i < N; i++) {
        left = 100001 - masts[i].f;
        int l = left, r = 100000;
        int last_zero = -1;
        while (l <= r) {
            int mid = l + (r-l)/2;
            if (query(1, 1, 100000, mid) == 0) {
                last_zero = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }

        int q = query(1, 1, 100000, 100000);
        int R = 100000, L = left;
        int ans = -1;
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (query(1, 1, 100000, mid) != q) {
                ans = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        int need = masts[i].s;
        if (last_zero != -1) {
            increment(1, 1, 100000, max(left, last_zero - need + 1), last_zero);
            need -= last_zero - max(left, last_zero - need + 1) + 1;
        }

        if (need && ans != -1 && q != 1) {
            increment(1, 1, 100000, max(left, max(last_zero + 1, ans - need + 1)), ans);
            need -= ans - max(left, max(last_zero + 1, ans - need + 1)) + 1;
        }

        if (need)
            increment(1, 1, 100000, 100001 - need, 100000);
    }

    ll ans = 0;
    for (int i = 1; i <= 100000; i++) {
        ll q = query(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 15 ms 340 KB Output is correct
2 Correct 16 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Incorrect 12 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 1140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 1552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 2344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 3720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 3992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 578 ms 4288 KB Output isn't correct
2 Halted 0 ms 0 KB -