oj.uz

Submission #828907

# Submission time Handle Problem Language Result Execution time Memory
828907 2023-08-17T20:00:08 Z NK_ Lightning Rod (NOI18_lightningrod) C++17
80 / 100
 2000 ms 262144 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;

	vi L(N), R(N);
	for(int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		L[i] = x - y, R[i] = x + y;
	}

	vi ord(N); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		if (L[x] == L[y]) return R[x] > R[y];
		return L[x] < L[y];		
	});

	int r = -INF, ans = 0;
	for(auto& i : ord) {
		// cout << i << " " << L[i] << " " << R[i] << endl;
		if (r < R[i]) ans++, r = R[i];
	}

	cout << ans << nl;

	exit(0-0);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 226660 KB Output is correct
2 Correct 1364 ms 226012 KB Output is correct
3 Correct 1343 ms 219944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 316 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 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 316 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 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 316 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 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 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 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 316 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 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 44 ms 5988 KB Output is correct
15 Correct 39 ms 5924 KB Output is correct
16 Correct 32 ms 5204 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 213476 KB Output is correct
2 Correct 1450 ms 213272 KB Output is correct
3 Correct 1425 ms 208108 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 226660 KB Output is correct
2 Correct 1364 ms 226012 KB Output is correct
3 Correct 1343 ms 219944 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 320 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 240 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 44 ms 5988 KB Output is correct
18 Correct 39 ms 5924 KB Output is correct
19 Correct 32 ms 5204 KB Output is correct
20 Correct 1449 ms 213476 KB Output is correct
21 Correct 1450 ms 213272 KB Output is correct
22 Correct 1425 ms 208108 KB Output is correct
23 Execution timed out 2084 ms 262144 KB Time limit exceeded
24 Halted 0 ms 0 KB -