oj.uz

답안 #712089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
712089 2023-03-18T06:06:36 Z Pherokung Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 1608 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000005
#define F first
#define S second
#define int long long
int n,x[MAXN],y[MAXN],l[MAXN],r[MAXN],rod[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;
}

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();
	}
	
	sort(v.begin(),v.end(),oper);
	for(auto tw : v){
		int i = tw.S;
		if(!rod[i] && !rod[l[i]] && !rod[r[i]]){
			ans++;
		}
		rod[i] = 1;
	}
	
	printf("%d",ans);
}

Compilation message

lightningrod.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~
lightningrod.cpp: In function 'int main()':
lightningrod.cpp:15:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   15 |  scanf("%d",&n);
      |         ~^  ~~
      |          |  |
      |          |  long long int*
      |          int*
      |         %lld
lightningrod.cpp:17:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   17 |   scanf("%d%d",&x[i],&y[i]);
      |          ~^    ~~~~~
      |           |    |
      |           int* long long int*
      |          %lld
lightningrod.cpp:17:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   17 |   scanf("%d%d",&x[i],&y[i]);
      |            ~^        ~~~~~
      |             |        |
      |             int*     long long int*
      |            %lld
lightningrod.cpp:62:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   62 |  printf("%d",ans);
      |          ~^  ~~~
      |           |  |
      |           |  long long int
      |           int
      |          %lld
lightningrod.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
lightningrod.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d%d",&x[i],&y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1608 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 77 ms 10548 KB Output is correct
15 Correct 76 ms 10992 KB Output is correct
16 Correct 64 ms 11212 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1596 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1608 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -