Submission #783723

#	Time	Username	Problem	Language	Result	Execution time	Memory
783723		chanhchuong123	Sails (IOI07_sails)	C++14	100 / 100	50 ms	3772 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define task ""
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int MAX = 100100;
const int CC = 100000;
int n;
pair<int, int> a[MAX];

int bit[MAX];
void updateValue(int id, int delta) {
    for (; id <= CC; id += id & -id)
        bit[id] += delta;
}
void updateValue(int l, int r, int delta) {
    if (l > r) return;
    updateValue(l, +delta);
    updateValue(r + 1, -delta);
}
int getValue(int id) {
    int res = 0;
    for (; id > 0; id -= id & -id)
        res += bit[id];
    return res;
}
int getPos(int value) {
    int cur = 0, curValue = 0;
    for (int j = 16; j >= 0; --j) if (cur + (1 << j) <= CC) {
        if (curValue + bit[cur + (1 << j)] <= value) {
            cur += 1 << j; curValue += bit[cur];
        }
    }
    return cur;
}

long long bit1[MAX];
long long bit2[MAX];
void updateSum(long long bit[], int id, long long delta) {
    for (; id <= CC; id += id & -id)
        bit[id] += delta;
}
void updateSum(int l, int r, long long delta) {
    if (l > r) return;
    updateSum(bit1, l, +delta);
    updateSum(bit1, r + 1, -delta);
    updateSum(bit2, l, +1LL * l * delta);
    updateSum(bit2, r + 1, -1LL * (r + 1) * delta);
}
long long getSum(long long bit[], int id) {
    long long res = 0;
    for (; id > 0; id -= id & -id)
        res += bit[id];
    return res;
}
long long getSum(int u) { return 1LL * (u + 1) * getSum(bit1, u) - getSum(bit2, u); }
long long getSum(int u, int v) { return getSum(v) - getSum(u - 1); }


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + 1 + n);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int h = a[i].first, k = a[i].second;
        h = CC - h + 1;
        ans += getSum(h, h + k - 1);
        int lastValue = getValue(h + k - 1);
        int lt = getPos(lastValue - 1), rt = getPos(lastValue);
        if (lt < h) {
            updateSum(rt - k + 1, rt, +1);
            updateValue(rt - k + 1, rt, +1);
        } else {
            updateSum(h, lt, +1); updateValue(h, lt, +1); k -= lt - h + 1;
            updateSum(rt - k + 1, rt, +1); updateValue(rt - k + 1, rt, +1);
        }
    }
    cout << ans;
	return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen(task".out", "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