Submission #1200113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200113		henrlly	Sails (IOI07_sails)	C++20	100 / 100	63 ms	1864 KiB

sails

// time-limit: 3000
#include <bits/stdc++.h>
#include <vector>

using namespace std;

#define ll long long

using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;

void setIO(string name = "") {
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void solve() {
    return;
}

vll bit;
int hmax;


void add(int i, ll x) {
    i++;
    while (i <= hmax) {
        bit[i] += x;
        i += i & -i;
    }
}

ll pref(int i) {
    i++;
    ll res = 0;
    while (i > 0) {
        res += bit[i];
        i -= i & -i;
    }
    return res;
}

// returns the first index in the bit that is less than x
// returns high if there is nothing before high is less than x
int bins(ll x, int high) {
    int low = 0;
    while (low < high) {
        int mid = (low + high) / 2;
        pref(mid) < x ? high = mid : low = mid + 1;
    }
    return low;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // setIO("test");

    int n; cin >> n;
    vector<pair<int,int>> v(n);

    for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;

    sort(v.begin(), v.end());
    hmax = v[v.size()-1].first; // h is 1-indexed, so no need to add 1 even though bit uses difference array

    // bit is monotonic decreasing
    bit.resize(hmax+1);

    // h is 1-indexed
    for (auto [h, k]: v) {
        ll last = pref(h-k); // h-k is the first index that should be added (before the mod)
        int i1 = bins(last, h); // i1 to h is the range where bit[i1] > last, h >= i1 > h-k
        int i2 = bins(last+1, h); // bit[i2] is the first index that == last, 1 <= i2 <= h-k
        add(i1, 1);
        add(h, -1);
        add(i2, 1);
        add(i2+k-(h-i1), -1);
    }

    ll res = 0;
    for (int i = 0; i < hmax; i++) res += (pref(i) * (pref(i) - 1)) / 2;

    cout << res << endl;

    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'void setIO(std::string)':
sails.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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