oj.uz

Submission #712089

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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