oj.uz

Submission #783720

# Submission time Handle Problem Language Result Execution time Memory
783720 2023-07-15T08:56:50 Z chanhchuong123 Sails (IOI07_sails) C++14
5 / 100
 45 ms 3396 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;

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;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int h, k;
        cin >> h >> k;
        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:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 3128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 3296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 3396 KB Output isn't correct
2 Halted 0 ms 0 KB -