답안 #692886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
692886	2023-02-02T06:55:54 Z	saayan007	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2000 ms	262144 KB

lightningrod

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define fur(i, a, b) for(ll i = a; i <= (ll) b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll) b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define nl "\n"

const ll inf = 1e12L;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;

    pl a[n + 2];
#define x first
#define y second
    fur(i, 1, n) {
        cin >> a[i].x >> a[i].y;
    }
    a[0] = a[n + 1] = {0, 0};
    sort(a + 1, a + n + 1);

    bool under[n + 1] = {};
    ll mx = -inf;
    ruf(i, n, 1) {
        if(a[i].y - a[i].x <= mx) {
            under[i] = 1;
        } else {
            mx = a[i].y - a[i].x;
        }
    }

    mx = -inf;
    fur(i, 1, n) {
        if(a[i].y + a[i].x <= mx) {
            under[i] = 1;
        } else {
            mx = a[i].y + a[i].x;
        }
    }

    ll ans = n;
    fur(i, 1, n) {
        if(under[i])
            --ans;
    }
    cout << ans <<nl;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1490 ms	161520 KB	Output is correct
2	Correct	1473 ms	160932 KB	Output is correct
3	Correct	1497 ms	156604 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	1 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	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	1 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	1 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	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	1 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	1 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	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	38 ms	3336 KB	Output is correct
15	Correct	49 ms	4972 KB	Output is correct
16	Correct	49 ms	4200 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1597 ms	165964 KB	Output is correct
2	Correct	1657 ms	165856 KB	Output is correct
3	Correct	1569 ms	161868 KB	Output is correct

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1490 ms	161520 KB	Output is correct
2	Correct	1473 ms	160932 KB	Output is correct
3	Correct	1497 ms	156604 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 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	1 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	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	38 ms	3336 KB	Output is correct
18	Correct	49 ms	4972 KB	Output is correct
19	Correct	49 ms	4200 KB	Output is correct
20	Correct	1597 ms	165964 KB	Output is correct
21	Correct	1657 ms	165856 KB	Output is correct
22	Correct	1569 ms	161868 KB	Output is correct
23	Correct	1958 ms	262144 KB	Output is correct
24	Execution timed out	2023 ms	262144 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-