oj.uz

답안 #118108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118108 2019-06-18T08:00:10 Z davitmarg Global Warming (CEOI18_glo) C++17
0 / 100
 1066 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, mx, 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);
		mx = max(mx, a[i]);
	}
	mx += x+10;
	build();
	for (int i = 1; i <= n; i++)
	{
		add(1, 1, mx, a[i] + x, get(1, 1, mx, a[i] + x - 1) + 1);
		add(1, 1, mx, a[i] + x, get(0, 1, mx, a[i] + x - 1) + 1);
		add(0, 1, mx, a[i], get(0, 1, mx, a[i] - 1) + 1);
	}

	cout << get(1, 1, mx, mx) << endl;

	return 0;
}


/*



*/

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:86: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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 603 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 603 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 603 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1066 ms 132708 KB Output is correct
2 Correct 1061 ms 132668 KB Output is correct
3 Correct 1018 ms 132636 KB Output is correct
4 Correct 1038 ms 132744 KB Output is correct
5 Runtime error 622 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 37152 KB Output is correct
2 Correct 260 ms 37084 KB Output is correct
3 Correct 247 ms 37088 KB Output is correct
4 Runtime error 698 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 402 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 603 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -