oj.uz

Submission #550931

# Submission time Handle Problem Language Result Execution time Memory
550931 2022-04-19T11:59:49 Z AKiko Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 1781 ms 147624 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ss second
#define ff first
#define pb push_back
#define pii pair<int, int>
#define INF INT_MAX
using namespace std;
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef AKIKO_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll MOD = 1e9 + 7;








int main() {
    FAST
    int n, mx = -1;
    cin >> n;
    stack<int> s;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if(mx >= x + y) {
            continue;
        }
        mx = x + y;
        int d = x - y;
        while(s.size() > 0) {
            if(s.top() >= d)
                s.pop();
            else break;
        }
        s.push(d);
    }
    cout << s.size() << "\n";

    

    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 39992 KB Output is correct
2 Correct 1319 ms 40116 KB Output is correct
3 Correct 1275 ms 38780 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 0 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 1 ms 212 KB Output is correct
7 Correct 1 ms 320 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 0 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 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 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 0 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 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 352 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 0 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 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 47 ms 3876 KB Output is correct
15 Correct 37 ms 3612 KB Output is correct
16 Correct 36 ms 3332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 25872 KB Output is correct
2 Correct 1293 ms 25824 KB Output is correct
3 Correct 1330 ms 25140 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 39992 KB Output is correct
2 Correct 1319 ms 40116 KB Output is correct
3 Correct 1275 ms 38780 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 1 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 1 ms 352 KB Output is correct
17 Correct 47 ms 3876 KB Output is correct
18 Correct 37 ms 3612 KB Output is correct
19 Correct 36 ms 3332 KB Output is correct
20 Correct 1315 ms 25872 KB Output is correct
21 Correct 1293 ms 25824 KB Output is correct
22 Correct 1330 ms 25140 KB Output is correct
23 Correct 1781 ms 147624 KB Output is correct
24 Correct 1762 ms 128932 KB Output is correct
25 Correct 1646 ms 116876 KB Output is correct