oj.uz

Submission #190364

# Submission time Handle Problem Language Result Execution time Memory
190364 2020-01-14T07:45:31 Z mrtsima22 Lightning Rod (NOI18_lightningrod) C++17
80 / 100
 2000 ms 129080 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define two pair<int,int>
#define pb push_back
#define f first
#define s second
#define sz(container) (int)(container.size())

inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
int n;
stack<two>st;
int main(){
n=bin();
while(n--){
	int x=bin();
	int y=bin();
	bool ok=1;
	while(sz(st)){
		int a=st.top().f;
		int b=st.top().s;
		if(x-a<=b-y){
			ok=0;
			break;
		}
		if(x-a<=y-b){
			st.pop();
		}else{
			break;
		}
	}
	if(ok){
		st.push({x,y});
	}
}
cout<<sz(st)<<endl;

	// you should actually read the stuff at the bottom
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), slow multiset operations
	* do smth instead of nothing and stay organized
	* unordered_map, hash_map, scanf, calculate answer instead of ans*K
*/
/*


                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1767 ms 127976 KB Output is correct
2 Correct 1781 ms 123156 KB Output is correct
3 Correct 1733 ms 129080 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 356 KB Output is correct
10 Correct 2 ms 396 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 356 KB Output is correct
10 Correct 2 ms 396 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 372 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 292 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 356 KB Output is correct
10 Correct 2 ms 396 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 372 KB Output is correct
14 Correct 55 ms 3932 KB Output is correct
15 Correct 53 ms 3672 KB Output is correct
16 Correct 46 ms 3776 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 104324 KB Output is correct
2 Correct 1554 ms 107608 KB Output is correct
3 Correct 1521 ms 105952 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1767 ms 127976 KB Output is correct
2 Correct 1781 ms 123156 KB Output is correct
3 Correct 1733 ms 129080 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 292 KB Output is correct
8 Correct 2 ms 356 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 396 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 372 KB Output is correct
17 Correct 55 ms 3932 KB Output is correct
18 Correct 53 ms 3672 KB Output is correct
19 Correct 46 ms 3776 KB Output is correct
20 Correct 1551 ms 104324 KB Output is correct
21 Correct 1554 ms 107608 KB Output is correct
22 Correct 1521 ms 105952 KB Output is correct
23 Execution timed out 2045 ms 88632 KB Time limit exceeded
24 Halted 0 ms 0 KB -