oj.uz

Submission #349244

# Submission time Handle Problem Language Result Execution time Memory
349244 2021-01-17T08:21:32 Z parsabahrami Sails (IOI07_sails) C++17
100 / 100
 67 ms 3052 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10;
int F[N], H[N], K[N], id[N], n; ll ret;

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

int get(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos) res += F[pos];
    return res;
}

int Find(int x) {
    int res = 0, sum = 0;
    for (int i = 19; ~i; i--) {
        res += (1 << i);
        if (res < N && sum + F[res] > x) sum += F[res];
        else res -= (1 << i);
    }
    return res + 1;
}

inline void add(int l, int r) {
    if (r < l) return;
    upd(l, 1), upd(r + 1, -1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &H[i], &K[i]);
        id[i] = i;
    }
    sort(id + 1, id + n + 1, [&](int i, int j) {
        return H[i] < H[j];
    });
    for (int i = 1; i <= n; i++) {
        int h = H[id[i]], k = K[id[i]];
        int x = get(h - k + 1); int l = Find(x), r = Find(x - 1);
        r = min(r, h + 1);
        //printf("%d %d %d %d %d\n", h, k, x, l, r);
        add(r, h), add(l, l + r - (h - k + 1) - 1);
    }
    for (int i = 1; i < N; i++) {
        int x = get(i);
        ret += 1ll * x * (x - 1) / 2;
    }
    printf("%lld\n", ret);
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 2 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 18 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1644 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2648 KB Output is correct
2 Correct 44 ms 2540 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2724 KB Output is correct
2 Correct 46 ms 2412 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3052 KB Output is correct
2 Correct 47 ms 2668 KB Output is correct