답안 #930289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930289	2024-02-19T09:20:35 Z	vjudge1	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1361 ms	247948 KB

lightningrod

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

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 1e7+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n;
pii a[SZ];
vector<int> vec;

bool check(int i, int j)
{
    return abs(a[i].fi - a[j].fi) <= a[i].se - a[j].se;
}

int main()
{
    init();
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        if(!vec.empty() && check(vec.back(), i)) continue;
        while(!vec.empty() && check(i, vec.back())) vec.pop_back();
        vec.pb(i);
    }
    cout << vec.size();
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1108 ms	219248 KB	Output is correct
2	Correct	1111 ms	231556 KB	Output is correct
3	Correct	1107 ms	231016 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	28 ms	2956 KB	Output is correct
15	Correct	27 ms	2652 KB	Output is correct
16	Correct	26 ms	3296 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1149 ms	192592 KB	Output is correct
2	Correct	1142 ms	199672 KB	Output is correct
3	Correct	1118 ms	196324 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1108 ms	219248 KB	Output is correct
2	Correct	1111 ms	231556 KB	Output is correct
3	Correct	1107 ms	231016 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	28 ms	2956 KB	Output is correct
18	Correct	27 ms	2652 KB	Output is correct
19	Correct	26 ms	3296 KB	Output is correct
20	Correct	1149 ms	192592 KB	Output is correct
21	Correct	1142 ms	199672 KB	Output is correct
22	Correct	1118 ms	196324 KB	Output is correct
23	Correct	1361 ms	247948 KB	Output is correct
24	Correct	1290 ms	228836 KB	Output is correct
25	Correct	1233 ms	211144 KB	Output is correct