Submission #118111

#	Time	Username	Problem	Language	Result	Execution time	Memory
118111		davitmarg	Global Warming (CEOI18_glo)	C++17	58 / 100	1051 ms	262144 KiB

glo

/*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, 0, mx, a[i] + x, get(1, 0, mx, a[i] + x - 1) + 1);
		add(1, 0, mx, a[i] + x, get(0, 0, mx, a[i] + x - 1) + 1);
		add(0, 0, mx, a[i], get(0, 0, mx, a[i] - 1) + 1);
	}

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

	return 0;
}


/*

3 1
1 1 3

*/

Compilation message (stderr)

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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25