oj.uz

Submission #305497

# Submission time Handle Problem Language Result Execution time Memory
305497 2020-09-23T10:59:35 Z Akashi Sails (IOI07_sails) C++14
100 / 100
 72 ms 3068 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

struct poles{
    int h, k;
    bool operator < (const poles &aux)const{
        return h < aux.h;
    }
};

poles a[DIM];

int n, mx, now;
int sp[DIM], aib[DIM];

void update(int pos, int val) {
    sp[pos] += val;
    for (int i = pos; i <= mx ; i = i + (i & (-i)))
        aib[i] += val;
}

int query(int pos) {
    int ans = 0;
    for (int i = pos; i > 0 ; i = i - (i & (-i)))
        ans += aib[i];
    return ans;
}

int find_left(int val) {
    int ans = 0, sum = 0;
    for (int bit = (1 << 30); bit >= 1 ; bit = bit >> 1) {
        if (ans + bit > now) continue ;
        if (sum + aib[ans | bit] > val) ans |= bit, sum += aib[ans];
    }

    return ans + 1;
}

int find_right(int val) {
    int ans = 0, sum = 0;
    for (int bit = (1 << 30); bit >= 1 ; bit = bit >> 1) {
        if (ans + bit > now) continue ;
        if (sum + aib[ans | bit] >= val) ans |= bit, sum += aib[ans];
    }

    return ans;
}

int main()
{
    #ifdef HOME
    freopen("sails.in", "r", stdin);
    freopen("sails.out", "w", stdout);
    #endif // HOME

    scanf("%d", &n);
    for (int i = 1; i <= n ; ++i) {
        scanf("%d%d", &a[i].h, &a[i].k);
        mx = max(mx, a[i].h);
    }

    ++mx;
    sort(a + 1, a + n + 1);
    now = 1;
    for (int i = 1; i <= n ; ++i) {
        while (now < a[i].h) ++now;

        int ind = now - a[i].k + 1;
        int val = query(ind);
        int l = find_left(val), r = find_right(val);

        if (l == ind) {
            update(ind, 1);
            update(now + 1, -1);
        } else {
            int cnt = r - ind + 1;

            update(l, 1);
            update(l + cnt, -1);

            if (r + 1 <= now) {
                update(r + 1, 1);
                update(now + 1, -1);
            }
        }
    }

    long long Sol = 0;
    for (int i = 1; i <= mx ; ++i) {
        sp[i] += sp[i - 1];
        Sol = Sol + 1LL * sp[i] * (sp[i] - 1) / 2;
    }

    printf("%lld", Sol);

    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 672 KB Output is correct
2 Correct 17 ms 896 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1656 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2552 KB Output is correct
2 Correct 48 ms 2680 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2808 KB Output is correct
2 Correct 50 ms 2424 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3068 KB Output is correct
2 Correct 46 ms 2424 KB Output is correct