oj.uz

Submission #197516

# Submission time Handle Problem Language Result Execution time Memory
197516 2020-01-21T13:28:22 Z handlename Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 486 ms 166172 KB 
#include <bits/stdc++.h>
using namespace std;
inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

int x,y;
stack<pair<int,int> > chosen;

int main(){
	int n=readInt();
	for (int i = 0; i < n; i++) {
		x = readInt();
		y = readInt();
        if (!chosen.empty() && x-chosen.top().first<=chosen.top().second-y) continue;
        while (!chosen.empty() && x-chosen.top().first<=y-chosen.top().second){
            chosen.pop();
        }
        chosen.push(make_pair(x,y));
    }
	cout<<chosen.size();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 166172 KB Output is correct
2 Correct 373 ms 159508 KB Output is correct
3 Correct 363 ms 156644 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 12 ms 3960 KB Output is correct
15 Correct 12 ms 3704 KB Output is correct
16 Correct 12 ms 3784 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 119196 KB Output is correct
2 Correct 384 ms 124432 KB Output is correct
3 Correct 364 ms 122328 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 166172 KB Output is correct
2 Correct 373 ms 159508 KB Output is correct
3 Correct 363 ms 156644 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 396 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 252 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 12 ms 3960 KB Output is correct
18 Correct 12 ms 3704 KB Output is correct
19 Correct 12 ms 3784 KB Output is correct
20 Correct 364 ms 119196 KB Output is correct
21 Correct 384 ms 124432 KB Output is correct
22 Correct 364 ms 122328 KB Output is correct
23 Correct 486 ms 142720 KB Output is correct
24 Correct 440 ms 154052 KB Output is correct
25 Correct 431 ms 137400 KB Output is correct