oj.uz

Submission #137687

# Submission time Handle Problem Language Result Execution time Memory
137687 2019-07-28T08:34:06 Z hamzqq9 Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 746 ms 228808 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;

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;
}

bitset<10000000> u;

int main() {

	int n;

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

	n=readInt();

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

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

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

		a[i].st=readInt();
		a[i].nd=readInt();

	}

	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);

	}

	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 450 ms 76296 KB Output is correct
2 Correct 447 ms 76016 KB Output is correct
3 Correct 436 ms 73976 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 252 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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 252 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 348 KB Output is correct
9 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 252 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 348 KB Output is correct
9 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 252 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 348 KB Output is correct
9 Correct 2 ms 256 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 16 ms 1784 KB Output is correct
15 Correct 16 ms 1912 KB Output is correct
16 Correct 16 ms 1784 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 79620 KB Output is correct
2 Correct 459 ms 79572 KB Output is correct
3 Correct 447 ms 77660 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 76296 KB Output is correct
2 Correct 447 ms 76016 KB Output is correct
3 Correct 436 ms 73976 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 252 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 256 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 256 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 16 ms 1784 KB Output is correct
18 Correct 16 ms 1912 KB Output is correct
19 Correct 16 ms 1784 KB Output is correct
20 Correct 463 ms 79620 KB Output is correct
21 Correct 459 ms 79572 KB Output is correct
22 Correct 447 ms 77660 KB Output is correct
23 Correct 746 ms 99336 KB Output is correct
24 Correct 710 ms 228808 KB Output is correct
25 Correct 670 ms 209976 KB Output is correct