oj.uz

Submission #712091

# Submission time Handle Problem Language Result Execution time Memory
712091 2023-03-18T06:10:17 Z Pherokung Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 1992 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000005
#define F first
#define S second
int n,x[MAXN],y[MAXN],l[MAXN],r[MAXN],ans=0;
vector<pair<int,int> > v;
deque<int> dq;
bool oper(pair<int,int> i,pair<int,int> j){
	return i.F > j.F;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		v.push_back({y[i],i});
	}
	
	for(int i=1;i<=n;i++){
		while(!dq.empty()){
			int p = dq.front();
			if(y[i] - x[i] >= y[p] - x[p]){
				r[p] = i;
				dq.pop_front();
			}
			else break;
		}
		dq.push_front(i);
	}
	while(!dq.empty()){
		r[dq.front()] = n+1;
		dq.pop_front();
	}
	
	for(int i=n;i>=1;i--){
		while(!dq.empty()){
			int p = dq.front();
			if(y[i] + x[i] >= y[p] + x[p]){
				l[p] = i;
				dq.pop_front();
			}
			else break;
		}
		dq.push_front(i);
	}
	while(!dq.empty()){
		l[dq.front()] = 0;
		dq.pop_front();
	}
	
	memset(x,0,sizeof x);
	sort(v.begin(),v.end(),oper);
	for(auto tw : v){
		int i = tw.S;
		if(!x[i] && !x[l[i]] && !x[r[i]]){
			ans++;
		}
		x[i] = 1;
	}
	
	printf("%d",ans);
}

Compilation message

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
lightningrod.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d%d",&x[i],&y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1992 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 15 ms 39412 KB Output is correct
3 Correct 15 ms 39408 KB Output is correct
4 Correct 15 ms 39380 KB Output is correct
5 Correct 19 ms 39436 KB Output is correct
6 Correct 16 ms 39380 KB Output is correct
7 Correct 15 ms 39428 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 15 ms 39412 KB Output is correct
3 Correct 15 ms 39408 KB Output is correct
4 Correct 15 ms 39380 KB Output is correct
5 Correct 19 ms 39436 KB Output is correct
6 Correct 16 ms 39380 KB Output is correct
7 Correct 15 ms 39428 KB Output is correct
8 Correct 16 ms 39380 KB Output is correct
9 Correct 17 ms 39380 KB Output is correct
10 Correct 17 ms 39340 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 15 ms 39412 KB Output is correct
3 Correct 15 ms 39408 KB Output is correct
4 Correct 15 ms 39380 KB Output is correct
5 Correct 19 ms 39436 KB Output is correct
6 Correct 16 ms 39380 KB Output is correct
7 Correct 15 ms 39428 KB Output is correct
8 Correct 16 ms 39380 KB Output is correct
9 Correct 17 ms 39380 KB Output is correct
10 Correct 17 ms 39340 KB Output is correct
11 Correct 16 ms 39472 KB Output is correct
12 Correct 17 ms 39500 KB Output is correct
13 Correct 16 ms 39456 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 15 ms 39412 KB Output is correct
3 Correct 15 ms 39408 KB Output is correct
4 Correct 15 ms 39380 KB Output is correct
5 Correct 19 ms 39436 KB Output is correct
6 Correct 16 ms 39380 KB Output is correct
7 Correct 15 ms 39428 KB Output is correct
8 Correct 16 ms 39380 KB Output is correct
9 Correct 17 ms 39380 KB Output is correct
10 Correct 17 ms 39340 KB Output is correct
11 Correct 16 ms 39472 KB Output is correct
12 Correct 17 ms 39500 KB Output is correct
13 Correct 16 ms 39456 KB Output is correct
14 Correct 83 ms 43164 KB Output is correct
15 Correct 92 ms 43296 KB Output is correct
16 Correct 77 ms 43440 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1991 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1992 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -