oj.uz

Submission #99101

# Submission time Handle Problem Language Result Execution time Memory
99101 2019-02-28T18:10:04 Z thiago4532 Global Warming (CEOI18_glo) C++17
28 / 100
 2000 ms 2788 KB 
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxv = 2e9 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;
int n, x;
int dp[maxn], dp2[maxn], v[maxn];

struct node{
	int v;
	node *l, *r;
	node(int v=-inf): v(v), l(0), r(0) {}
};

void update(node* no, int p, int v, int ini=-maxv, int fim=maxv){
	if(ini == fim){
		no->v = v;
		return;
	}

	int meio = (ini+fim)>>1;
	if(p <= meio){
		if(!no->l) no->l = new node;
		update(no->l, p, v, ini, meio);
	}else{
		if(!no->r) no->r = new node;
		update(no->r, p, v, meio+1, fim);
	}
	no->v = (no->l?no->l->v:-inf), (no->r?no->r->v:-inf);
}

int query(node* no, int l, int r, int ini=-maxv, int fim=maxv){
	if(!no || ini > r || fim < l) return -inf;
	else if(l <= ini && fim <= r) return no->v;

	int meio = (ini+fim)>>1;
	int p1 = (no->l?query(no->l, l, r, ini, meio):-inf);
	int p2 = (no->r?query(no->r, l, r, meio+1, fim):-inf);
	return max(p1, p2);
}

int32_t main() {
	cin >> n >> x;
	for(int i=1;i<=n;i++)
		cin >> v[i];

	dp[1] = 1, dp2[1] = 1;
	node *n1 = new node, *n2 = new node;

	for(int i=2;i<=n;i++){
		dp[i] = dp2[i] = 1;

		// dp[i] = 1 + query(n1, -maxv, v[i]-1);
		// dp2[i] = 1 + max(query(n1, -maxv, v[i]-x-1), query(n2, -maxv, v[i]));
		for(int j=1;j<i;j++){
			if(v[j] - x >= v[i]) continue;
			dp2[i] = max(dp2[i], 1 + dp[j]);
			if(v[j] >= v[i]) continue;
			dp[i] = max(dp[i], 1 + dp[j]);
			dp2[i] = max(dp2[i], 1 + dp2[j]);
		}
		
	}

	int ans=0;
	for(int i=1;i<=n;i++)
		ans = max(ans, dp2[i]);

	cout << ans << "\n";
	return 0;
}

Compilation message

glo.cpp: In function 'void update(node*, int64_t, int64_t, int64_t, int64_t)':
glo.cpp:31:47: warning: second operand of conditional expression has no effect [-Wunused-value]
  no->v = (no->l?no->l->v:-inf), (no->r?no->r->v:-inf);
                                        ~~~~~~~^
glo.cpp:31:49: warning: third operand of conditional expression has no effect [-Wunused-value]
  no->v = (no->l?no->l->v:-inf), (no->r?no->r->v:-inf);
                                                 ^~~~
glo.cpp: In function 'int32_t main()':
glo.cpp:50:8: warning: unused variable 'n1' [-Wunused-variable]
  node *n1 = new node, *n2 = new node;
        ^~
glo.cpp:50:24: warning: unused variable 'n2' [-Wunused-variable]
  node *n1 = new node, *n2 = new node;
                        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 408 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 428 KB Output is correct
18 Correct 2 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 408 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 428 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 4 ms 372 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 4 ms 512 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 2788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 1508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 408 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 428 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 4 ms 372 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 4 ms 512 KB Output is correct
27 Execution timed out 2023 ms 2788 KB Time limit exceeded
28 Halted 0 ms 0 KB -