Submission #349244

#	Time	Username	Problem	Language	Result	Execution time	Memory
349244		parsabahrami	Sails (IOI07_sails)	C++17	100 / 100	67 ms	3052 KiB

sails

// 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 (stderr)

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 / 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