oj.uz

Submission #692696

# Submission time Handle Problem Language Result Execution time Memory
692696 2023-02-02T04:30:44 Z zeroesandones Lightning Rod (NOI18_lightningrod) C++17
66 / 100
 1261 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back

struct BIT {
    ll n;
    vi tree;

    BIT(ll N) {
        n = N;
        tree.resize(n, 0);
    }

    void add(ll x, ll k) {
        while(k <= n) {
            tree[k] += x;
            k += k&-k;
        }
    }

    ll get(ll k) {
        ll sum = 0;
        while(k >= 1) {
            sum += tree[k];
            k -= k&-k;
        }

        return sum;
    }
};

void solve()
{
    ll n;
    cin >> n;

    ll x[n + 1], y[n + 1];
    FOR(i, 1, n + 1) {
        cin >> x[i] >> y[i];
    }

    vector<array<ll, 3>> a(n + 1);
    for(int i = 1; i <= n; ++i) {
        a[i] = {x[i], y[i], i};
    }

    ll left[n + 1] = {}, right[n + 1] = {};
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j >= 1; --j) {
            if(abs(x[j] - x[i]) <= y[i] - y[j])
                left[i] = j;
            else
                break;
        }

        for(int j = i; j <= n; ++j) {
            if(abs(x[j] - x[i]) <= y[i] - y[j])
                right[i] = j;
            else
                break;
        }
    }

    sort(1 + all(a), [&](array<ll, 3> lhs, array<ll, 3> rhs) {
        return lhs[1] > rhs[1];
            });

    ll ans = 0;
    BIT bit(n + 5);
    for(int i = 1; i <= n; ++i) {
        if(bit.get(a[i][2])) continue;
        ++ans;
        bit.add(1, left[a[i][2]]);
        bit.add(-1, right[a[i][2]] + 1);
    }

    cout << ans << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 65 ms 14304 KB Output is correct
15 Correct 68 ms 14896 KB Output is correct
16 Correct 67 ms 14152 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -