oj.uz

Submission #599888

# Submission time Handle Problem Language Result Execution time Memory
599888 2022-07-20T05:55:16 Z starchan Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 555 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
inline int readInt()
{
	int x = 0; char ch=getchar_unlocked(); bool st = 1;
	while(ch < '0'  || ch > '9'){if(ch=='-')st=0; ch=getchar_unlocked();}
	while(ch>='0'&&ch<='9'){x = (x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
	return st?x:-x;
}
vector<int> add(1e7+1, 0);
vector<int> sub(1e7+1, 0);
signed main()
{
	fast();
	int n = readInt();
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		x = readInt();
		y = readInt();
		add[i] = x+y;
		sub[i] = y-x;
		if(i > 1)
			add[i] = max(add[i], add[i-1]);
	}
	int ans = 0;
	for(int i = n; i >= 1; i--)
	{
		ans+=(((i==1)||(add[i] > add[i-1]))&&((i==n)||(sub[i] > sub[i+1])));
		if(i < n)
			sub[i] = max(sub[i], sub[i+1]);
	}
	cout << ans;
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 156848 KB Output is correct
2 Correct 310 ms 164152 KB Output is correct
3 Correct 298 ms 161044 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 156748 KB Output is correct
2 Correct 57 ms 156844 KB Output is correct
3 Correct 64 ms 156748 KB Output is correct
4 Correct 58 ms 156772 KB Output is correct
5 Correct 58 ms 156800 KB Output is correct
6 Correct 58 ms 156748 KB Output is correct
7 Correct 63 ms 156840 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 156748 KB Output is correct
2 Correct 57 ms 156844 KB Output is correct
3 Correct 64 ms 156748 KB Output is correct
4 Correct 58 ms 156772 KB Output is correct
5 Correct 58 ms 156800 KB Output is correct
6 Correct 58 ms 156748 KB Output is correct
7 Correct 63 ms 156840 KB Output is correct
8 Correct 59 ms 156900 KB Output is correct
9 Correct 61 ms 156840 KB Output is correct
10 Correct 58 ms 156868 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 156748 KB Output is correct
2 Correct 57 ms 156844 KB Output is correct
3 Correct 64 ms 156748 KB Output is correct
4 Correct 58 ms 156772 KB Output is correct
5 Correct 58 ms 156800 KB Output is correct
6 Correct 58 ms 156748 KB Output is correct
7 Correct 63 ms 156840 KB Output is correct
8 Correct 59 ms 156900 KB Output is correct
9 Correct 61 ms 156840 KB Output is correct
10 Correct 58 ms 156868 KB Output is correct
11 Correct 58 ms 156796 KB Output is correct
12 Correct 59 ms 156916 KB Output is correct
13 Correct 59 ms 156792 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 156748 KB Output is correct
2 Correct 57 ms 156844 KB Output is correct
3 Correct 64 ms 156748 KB Output is correct
4 Correct 58 ms 156772 KB Output is correct
5 Correct 58 ms 156800 KB Output is correct
6 Correct 58 ms 156748 KB Output is correct
7 Correct 63 ms 156840 KB Output is correct
8 Correct 59 ms 156900 KB Output is correct
9 Correct 61 ms 156840 KB Output is correct
10 Correct 58 ms 156868 KB Output is correct
11 Correct 58 ms 156796 KB Output is correct
12 Correct 59 ms 156916 KB Output is correct
13 Correct 59 ms 156792 KB Output is correct
14 Correct 69 ms 157112 KB Output is correct
15 Correct 71 ms 157128 KB Output is correct
16 Correct 64 ms 157132 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 156924 KB Output is correct
2 Correct 296 ms 156876 KB Output is correct
3 Correct 277 ms 156908 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 156848 KB Output is correct
2 Correct 310 ms 164152 KB Output is correct
3 Correct 298 ms 161044 KB Output is correct
4 Correct 59 ms 156748 KB Output is correct
5 Correct 57 ms 156844 KB Output is correct
6 Correct 64 ms 156748 KB Output is correct
7 Correct 58 ms 156772 KB Output is correct
8 Correct 58 ms 156800 KB Output is correct
9 Correct 58 ms 156748 KB Output is correct
10 Correct 63 ms 156840 KB Output is correct
11 Correct 59 ms 156900 KB Output is correct
12 Correct 61 ms 156840 KB Output is correct
13 Correct 58 ms 156868 KB Output is correct
14 Correct 58 ms 156796 KB Output is correct
15 Correct 59 ms 156916 KB Output is correct
16 Correct 59 ms 156792 KB Output is correct
17 Correct 69 ms 157112 KB Output is correct
18 Correct 71 ms 157128 KB Output is correct
19 Correct 64 ms 157132 KB Output is correct
20 Correct 283 ms 156924 KB Output is correct
21 Correct 296 ms 156876 KB Output is correct
22 Correct 277 ms 156908 KB Output is correct
23 Correct 545 ms 227084 KB Output is correct
24 Correct 555 ms 262144 KB Output is correct
25 Correct 543 ms 262144 KB Output is correct