oj.uz

Submission #367354

# Submission time Handle Problem Language Result Execution time Memory
367354 2021-02-16T23:33:58 Z ijxjdjd Sails (IOI07_sails) C++14
100 / 100
 352 ms 3048 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 100000;
int lzy[4*MAXN];
void inc(int l, int r, int n = 1, int tl = 0, int tr = MAXN-1) {
    if (r < tl || l > tr) {
        return;
    }
    if (l <= tl && tr <= r) {
        lzy[n]++;
    }
    else {
//        if (n == 1) {
//            cerr << "Upd: " << l << " " << r << endl;
//        }
        int tm = (tl + tr)/2;
        inc(l, r, 2*n, tl, tm);
        inc(l, r, 2*n+1, tm+1, tr);
    }
}
int query(int i, int sm = 0, int n = 1, int tl = 0, int tr = MAXN-1) {
    sm += lzy[n];
    if (tl == tr) {
        return sm;
    }
    else {
        int tm = (tl + tr)/2;
        if (i <= tm) {
            return query(i, sm, 2*n, tl, tm);
        }
        return query(i, sm, 2*n+1, tm+1, tr);
    }
}
ll c2(ll a) {
    return ((a)*(a-1))/2;
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	vector<pair<int, int>> masts;
	priority_queue<int, vector<int>, greater<int>> pq;
	FR(i, N) {
        int h, k;
        cin >> h >> k;
        masts.push_back({h, k});
	}
	sort(all(masts));
	ll ans = 0;
	FR(i, N) {
	    int v = query(masts[i].first - masts[i].second);
	    int l = -1, r = -1;
	    int low = 0, high = masts[i].first-masts[i].second;
	    while (low < high) {
            int mid = (low + high)/2;
            if (query(mid) == v) {
                high = mid;
            }
            else {
                low = mid+1;
            }
	    }
	    l = high;
	    low = masts[i].first-masts[i].second, high = masts[i].first-1;
	    while (low < high) {
            int mid = (low + high+1)/2;
            if (query(mid) == v) {
                low = mid;
            }
            else {
                high = mid-1;
            }
	    }
	    r = low;
	    inc(r+1, masts[i].first-1);
	    inc(l, (l + masts[i].second - ((masts[i].first-1) - (r+1) + 1) - 1));
    }
    FR(i, 100000) {
        ans += c2(query(i));
    }
    cout << ans << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 364 KB Output is correct
2 Correct 7 ms 492 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 364 KB Output is correct
2 Correct 8 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 492 KB Output is correct
2 Correct 10 ms 1388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 820 KB Output is correct
2 Correct 66 ms 1264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1008 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 1388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 2096 KB Output is correct
2 Correct 215 ms 3048 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 2408 KB Output is correct
2 Correct 117 ms 2536 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 2408 KB Output is correct
2 Correct 177 ms 2664 KB Output is correct