oj.uz

Submission #123113

# Submission time Handle Problem Language Result Execution time Memory
123113 2019-06-30T08:55:30 Z mechfrog88 Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 581 ms 227544 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	

inline int readInt() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	n = readInt();
	int arrx[n];
	int arry[n];
	stack <int> s;
	for (int z=0;z<n;z++){
		arrx[z] = readInt();
		arry[z] = readInt();
		int a = arrx[z]-arry[z];
		int b = arrx[z]+arry[z];
		if (s.empty()){
			s.emplace(z);
		}
		int c = arrx[s.top()]-arry[s.top()];
		int d = arrx[s.top()]+arry[s.top()];
		if (c <= a && b <= d) continue;
		else{
			while (a <= c && d <= b){
				s.pop();
				if (s.size() == 0) break;
				c = arrx[s.top()]-arry[s.top()];
				d = arrx[s.top()]+arry[s.top()];
			}
			s.emplace(z);
		}
	}
	printf("%d",int(s.size()));
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 118164 KB Output is correct
2 Correct 432 ms 117208 KB Output is correct
3 Correct 421 ms 114272 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 376 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 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 376 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 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 13 ms 2600 KB Output is correct
15 Correct 13 ms 2552 KB Output is correct
16 Correct 14 ms 2936 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 106008 KB Output is correct
2 Correct 446 ms 105644 KB Output is correct
3 Correct 467 ms 103340 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 118164 KB Output is correct
2 Correct 432 ms 117208 KB Output is correct
3 Correct 421 ms 114272 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 376 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 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 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 13 ms 2600 KB Output is correct
18 Correct 13 ms 2552 KB Output is correct
19 Correct 14 ms 2936 KB Output is correct
20 Correct 445 ms 106008 KB Output is correct
21 Correct 446 ms 105644 KB Output is correct
22 Correct 467 ms 103340 KB Output is correct
23 Correct 581 ms 107272 KB Output is correct
24 Correct 536 ms 227544 KB Output is correct
25 Correct 541 ms 208388 KB Output is correct