Submission #60541

#	Time	Username	Problem	Language	Result	Execution time	Memory
60541		aquablitz11	Sails (IOI07_sails)	C++14	100 / 100	98 ms	8804 KiB

sails

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int LN = 18;
const int N = 1<<LN;

int ft[1<<LN];

int get(int i) {
    int ans = 0;
    for (; i; i -= i&-i) ans += ft[i];
    return ans;
}

int pos(int x) {
    int i = 0, val = 0;
    for (int j = LN-1; j >= 0; --j) {
        int ni = i+(1<<j);
        if (val+ft[ni] >= x) {
            val += ft[ni];
            i = ni;
        }
    }
    return i;
}

void upd(int i, int x) {
    for (; i < N; i += i&-i)
        ft[i] += x;
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<pii> mast;
    for (int i = 0; i < n; ++i) {
        int h, k;
        scanf("%d%d", &h, &k);
        mast.emplace_back(h, k);
    }
    sort(mast.begin(), mast.end());
    for (int i = 0; i < n; ++i) {
        int h = mast[i].first, k = mast[i].second;
        int x = get(h-k+1);
        int p1 = min(h, pos(x)), p2 = min(h, pos(x+1));
        upd(p1+1, 1);
        upd(h+1, -1);
        upd(p2+1, 1);
        upd(p2+(k-h+p1)+1, -1);
    }
    ll ans = 0;
    for (int i = 1; i < N; ++i) {
        ll x = get(i);
        ans += x*(x-1)/2;
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sails.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &h, &k);
         ~~~~~^~~~~~~~~~~~~~~~

• 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