oj.uz

Submission #1110187

# Submission time Handle Problem Language Result Execution time Memory
1110187 2024-11-09T01:21:15 Z hqminhuwu Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 1312 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 1e7 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int n, a[N], b[N], cnt[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;

    forr (i, 1, n){
        cin >> a[i] >> b[i];
    }

    int mx = -1;

    forr (i, 1, n){
        if (mx >= a[i] + b[i]){
            cnt[i]++;
        }
        maxz(mx, a[i] + b[i]);
    }

    int mn = mod;

    ford (i, n, 1){
        if (mn <= a[i] - b[i]){
            cnt[i]++;
        }
        minz(mn, a[i] - b[i]);
     //   cout << mn << " " << a[i] - b[i] << endl;
    }

    int res = 0;

    forr (i, 1, n){
        res += (!cnt[i]);
    }

    cout << res << "\n";

    return 0;
}
/*



*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 972 ms 137156 KB Output is correct
2 Correct 1293 ms 190536 KB Output is correct
3 Correct 1020 ms 185548 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 2 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 2 ms 4608 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 27 ms 12368 KB Output is correct
15 Correct 29 ms 12104 KB Output is correct
16 Correct 27 ms 11460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 166924 KB Output is correct
2 Correct 1051 ms 213920 KB Output is correct
3 Correct 1080 ms 211496 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 972 ms 137156 KB Output is correct
2 Correct 1293 ms 190536 KB Output is correct
3 Correct 1020 ms 185548 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 1 ms 4432 KB Output is correct
13 Correct 1 ms 4432 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 2 ms 4608 KB Output is correct
16 Correct 2 ms 4432 KB Output is correct
17 Correct 27 ms 12368 KB Output is correct
18 Correct 29 ms 12104 KB Output is correct
19 Correct 27 ms 11460 KB Output is correct
20 Correct 1117 ms 166924 KB Output is correct
21 Correct 1051 ms 213920 KB Output is correct
22 Correct 1080 ms 211496 KB Output is correct
23 Correct 1312 ms 262144 KB Output is correct
24 Correct 1289 ms 262144 KB Output is correct
25 Correct 1260 ms 249476 KB Output is correct