oj.uz

Submission #137663

# Submission time Handle Problem Language Result Execution time Memory
137663 2019-07-28T08:23:41 Z hamzqq9 Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 211568 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 500005
#define MOD 1000000007
using namespace std;

void fastscan(int &number) 
{ 
    //variable to indicate sign of input number 
    bool negative = false; 
    register int c; 
  
    number = 0; 
  
    // extract current character from buffer 
    c = getchar(); 
    if (c=='-') 
    { 
        // number is negative 
        negative = true; 
  
        // extract the next character from the buffer 
        c = getchar(); 
    } 
  
    // Keep on extracting characters if they are integers 
    // i.e ASCII Value lies from '0'(48) to '9' (57) 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
  
    // if scanned input has a negative sign, negate the 
    // value of the input number 
    if (negative) 
        number *= -1; 
} 

int main() {

	int n;

	//scanf("%d",&n);

	fastscan(n);

	vector<ii> a(n);
	vector<bool> u(n);
	int cnt=n;

	for(int i=0;i<n;i++) {

		//scanf("%d %d",&a[i].st,&a[i].nd);

		fastscan(a[i].st);
		fastscan(a[i].nd);

	}

	sort(a.begin(),a.end());

	int mn=inf;

	for(int i=n-1;i>=0;i--) {

		int val=a[i].st-a[i].nd;

		if(mn<=val) {

			cnt-=!u[i];
			u[i]=1;

		}

		umin(mn,val);

	}

	for(int i=0;i<n;i++) {

		int b=i;

		while(i+1<n && a[i].st==a[i+1].st) i++;

		reverse(a.begin()+b,a.begin()+i+1);

	}

	int mx=-inf;

	for(int i=0;i<n;i++) {

		int val=a[i].st+a[i].nd;

		if(mx>=val) {

			cnt-=!u[i];
			u[i]=1;

		}

		umax(mx,val);

	}

	printf("%d",cnt);

}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1983 ms 79708 KB Output is correct
2 Correct 1998 ms 189404 KB Output is correct
3 Correct 1945 ms 184288 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 256 KB Output is correct
5 Correct 2 ms 256 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 256 KB Output is correct
5 Correct 2 ms 256 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 436 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 256 KB Output is correct
5 Correct 2 ms 256 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 436 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 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 256 KB Output is correct
5 Correct 2 ms 256 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 436 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 59 ms 1784 KB Output is correct
15 Correct 60 ms 1856 KB Output is correct
16 Correct 51 ms 1832 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1844 ms 79552 KB Output is correct
2 Correct 1861 ms 175736 KB Output is correct
3 Correct 1807 ms 171404 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1983 ms 79708 KB Output is correct
2 Correct 1998 ms 189404 KB Output is correct
3 Correct 1945 ms 184288 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 256 KB Output is correct
8 Correct 2 ms 256 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 436 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 59 ms 1784 KB Output is correct
18 Correct 60 ms 1856 KB Output is correct
19 Correct 51 ms 1832 KB Output is correct
20 Correct 1844 ms 79552 KB Output is correct
21 Correct 1861 ms 175736 KB Output is correct
22 Correct 1807 ms 171404 KB Output is correct
23 Execution timed out 2086 ms 211568 KB Time limit exceeded
24 Halted 0 ms 0 KB -