oj.uz

Submission #979138

# Submission time Handle Problem Language Result Execution time Memory
979138 2024-05-10T09:35:21 Z MilosMilutinovic Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 10000005;

int x[MAX], y[MAX], ord[MAX];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    x[i] = a - b;
    y[i] = a + b;
    ord[i] = i;
  }
  sort(ord, ord + n, [&](int i, int j) {
    if (x[i] != x[j]) {
      return x[i] < x[j];
    } else {
      return y[i] > y[j];
    }
  });
  int ans = 0, mx = -1;
  for (int i = 0; i < n; i++) {
    if (mx < y[ord[i]]) {
      ans += 1;
      mx = y[ord[i]];
    }
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1496 ms 217588 KB Output is correct
2 Correct 1424 ms 221076 KB Output is correct
3 Correct 1332 ms 219180 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4560 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4560 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 45 ms 12400 KB Output is correct
15 Correct 39 ms 12184 KB Output is correct
16 Correct 32 ms 11368 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1441 ms 211436 KB Output is correct
2 Correct 1513 ms 209480 KB Output is correct
3 Correct 1353 ms 207124 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1496 ms 217588 KB Output is correct
2 Correct 1424 ms 221076 KB Output is correct
3 Correct 1332 ms 219180 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4560 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 45 ms 12400 KB Output is correct
18 Correct 39 ms 12184 KB Output is correct
19 Correct 32 ms 11368 KB Output is correct
20 Correct 1441 ms 211436 KB Output is correct
21 Correct 1513 ms 209480 KB Output is correct
22 Correct 1353 ms 207124 KB Output is correct
23 Execution timed out 2041 ms 262144 KB Time limit exceeded
24 Halted 0 ms 0 KB -