oj.uz

Submission #817609

# Submission time Handle Problem Language Result Execution time Memory
817609 2023-08-09T13:57:04 Z serifefedartar Sails (IOI07_sails) C++17
5 / 100
 351 ms 4312 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 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;
        }

        if (ans == -1) {
            increment(1, 1, 100000, 100001-masts[i].s, 100000);
        } else {
            increment(1, 1, 100000, max(left, ans - masts[i].s + 1), ans);
            if (ans - masts[i].s + 1 < left) {
                increment(1, 1, 100000, 100000 - masts[i].s + ans - left + 2, 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 13 ms 340 KB Output is correct
2 Correct 14 ms 380 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 12 ms 368 KB Output is correct
2 Incorrect 12 ms 380 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 16 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 32 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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