Submission #367354

#	Time	Username	Problem	Language	Result	Execution time	Memory
367354		ijxjdjd	Sails (IOI07_sails)	C++14	100 / 100	352 ms	3048 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10