oj.uz

Submission #783723

# Submission time Handle Problem Language Result Execution time Memory
783723 2023-07-15T09:00:40 Z chanhchuong123 Sails (IOI07_sails) C++14
100 / 100
 50 ms 3772 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 12 ms 832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1108 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1680 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2768 KB Output is correct
2 Correct 36 ms 3772 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2936 KB Output is correct
2 Correct 36 ms 3364 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3004 KB Output is correct
2 Correct 37 ms 2760 KB Output is correct