oj.uz

Submission #118105

# Submission time Handle Problem Language Result Execution time Memory
118105 2019-06-18T07:57:39 Z davitmarg Global Warming (CEOI18_glo) C++17
0 / 100
 994 ms 262144 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,x,a[200005];
vector<int> t,L,R;

int addNode(int val=0)
{
	t.PB(val);
	L.PB(-1);
	R.PB(-1);
	return ((int)t.size() - 1);
}

void build()
{
	t.clear();
	addNode();
	addNode();
}

void add(int v, int l, int r, int pos,int val)
{
	if (l == r)
	{
		t[v] = max(t[v],val);
		return;
	}
	int m = (l + r) >> 1;
	if (L[v] == -1)
		L[v] = addNode();
	if (R[v] == -1)
		R[v] = addNode();
	if (pos <= m)
		add(L[v], l, m, pos, val);
	else
		add(R[v], m + 1, r, pos, val);
	t[v] = max(t[L[v]], t[R[v]]);
}

int get(int v,int l,int r,int pos)
{
	if (r == pos)
		return t[v];

	int m = (l + r) >> 1;
	if (L[v] == -1)
		L[v] = addNode();
	if (R[v] == -1)
		R[v] = addNode();

	if (pos <= m)
		return get(L[v], l, m, pos);
	else
		return max(t[L[v]], get(R[v], m + 1, r, pos));
}

int main()
{
	cin >> n >> x;
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	build();
	for (int i = 1; i <= n; i++)
	{
		add(1, 1, 2 * mod, a[i] + x, get(1, 1, 2 * mod, a[i] + x - 1) + 1);
		add(1, 1, 2 * mod, a[i] + x, get(0, 1, 2 * mod, a[i] + x - 1) + 1);
		add(0, 1, 2 * mod, a[i], get(0, 1, 2 * mod, a[i] - 1) + 1);
	}

	cout << get(1, 1, 2 * mod, 2 * mod) << endl;

	return 0;
}


/*



*/

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 134788 KB Output is correct
2 Correct 970 ms 134656 KB Output is correct
3 Correct 986 ms 134696 KB Output is correct
4 Correct 962 ms 134604 KB Output is correct
5 Runtime error 627 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 37668 KB Output is correct
2 Correct 245 ms 37772 KB Output is correct
3 Correct 254 ms 37600 KB Output is correct
4 Runtime error 642 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -