oj.uz

Submission #60541

# Submission time Handle Problem Language Result Execution time Memory
60541 2018-07-24T10:14:43 Z aquablitz11 Sails (IOI07_sails) C++14
100 / 100
 98 ms 8804 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int LN = 18;
const int N = 1<<LN;

int ft[1<<LN];

int get(int i) {
    int ans = 0;
    for (; i; i -= i&-i) ans += ft[i];
    return ans;
}

int pos(int x) {
    int i = 0, val = 0;
    for (int j = LN-1; j >= 0; --j) {
        int ni = i+(1<<j);
        if (val+ft[ni] >= x) {
            val += ft[ni];
            i = ni;
        }
    }
    return i;
}

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

int main()
{
    int n;
    scanf("%d", &n);
    vector<pii> mast;
    for (int i = 0; i < n; ++i) {
        int h, k;
        scanf("%d%d", &h, &k);
        mast.emplace_back(h, k);
    }
    sort(mast.begin(), mast.end());
    for (int i = 0; i < n; ++i) {
        int h = mast[i].first, k = mast[i].second;
        int x = get(h-k+1);
        int p1 = min(h, pos(x)), p2 = min(h, pos(x+1));
        upd(p1+1, 1);
        upd(h+1, -1);
        upd(p2+1, 1);
        upd(p2+(k-h+p1)+1, -1);
    }
    ll ans = 0;
    for (int i = 1; i < N; ++i) {
        ll x = get(i);
        ans += x*(x-1)/2;
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 488 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 728 KB Output is correct
2 Correct 7 ms 728 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 728 KB Output is correct
2 Correct 6 ms 728 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 824 KB Output is correct
2 Correct 9 ms 1188 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1188 KB Output is correct
2 Correct 25 ms 1536 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4124 KB Output is correct
2 Correct 73 ms 5012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6036 KB Output is correct
2 Correct 71 ms 6704 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 8116 KB Output is correct
2 Correct 80 ms 8804 KB Output is correct