oj.uz

Submission #1060641

# Submission time Handle Problem Language Result Execution time Memory
1060641 2024-08-15T20:11:12 Z oviyan_gandhi Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 532 ms 259904 KB 
#include <bits/stdc++.h>
using namespace std;

inline int readInt() {
    int x = 0;
    char ch = getchar();
    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[10000000], Y[10000000];
bool use[10000000];

// whether i contains j
bool contains(int i, int j){
    return abs(X[i] - X[j]) <= (Y[i] - Y[j]);
}

int main(){
	int N = readInt();
	for(int i = 0; i < N; i++) {
		X[i] = readInt();
		Y[i] = readInt();
        use[i] = true;
	}
    stack<int> s;
    for (int i = 0; i < N; i++){
        while (!s.empty() && !contains(s.top(), i))
            s.pop();
        if (!s.empty())
            use[i] = false;
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = N-1; i >= 0; i--){
        while (!s.empty() && !contains(s.top(), i))
            s.pop();
        if (!s.empty())
            use[i] = false;
        s.push(i);
    }
	cout << accumulate(use, use+N, 0) << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 200084 KB Output is correct
2 Correct 278 ms 199520 KB Output is correct
3 Correct 248 ms 196552 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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4492 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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4492 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4544 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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4492 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4544 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 4444 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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4492 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4544 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 4444 KB Output is correct
14 Correct 13 ms 14436 KB Output is correct
15 Correct 12 ms 14112 KB Output is correct
16 Correct 10 ms 13612 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 184552 KB Output is correct
2 Correct 326 ms 184872 KB Output is correct
3 Correct 309 ms 181136 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 200084 KB Output is correct
2 Correct 278 ms 199520 KB Output is correct
3 Correct 248 ms 196552 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 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4492 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4544 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 4444 KB Output is correct
17 Correct 13 ms 14436 KB Output is correct
18 Correct 12 ms 14112 KB Output is correct
19 Correct 10 ms 13612 KB Output is correct
20 Correct 307 ms 184552 KB Output is correct
21 Correct 326 ms 184872 KB Output is correct
22 Correct 309 ms 181136 KB Output is correct
23 Correct 532 ms 259904 KB Output is correct
24 Correct 502 ms 241220 KB Output is correct
25 Correct 517 ms 224260 KB Output is correct