Submission #118163

#	Time	Username	Problem	Language	Result	Execution time	Memory
118163		davitmarg	Global Warming (CEOI18_glo)	C++17	100 / 100	1018 ms	31468 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;

struct item
{
	int val, key, mxval;
	LL prior;
	item* l;
	item* r;
	item(int v = 0, int k = 0, LL p = (rand() << 16) + rand())
	{
		mxval = val = v;
		key = k;
		prior = p;
		l = r = NULL;
	}
};

typedef item* pitem;

int getVal(pitem t)
{
	return (!t) ? 0 : t->mxval;
}

void update(pitem t)
{
	if (!t)
		return;
	t->mxval = max(t->val, max(getVal(t->l), getVal(t->r)));
}

void split(pitem t, int key, pitem& l, pitem& r)
{
	if (!t)
		l = r = NULL;
	else if (t->key > key)
	{
		split(t->l, key, l, t->l);
		r = t;
	}
	else
	{
		split(t->r, key, t->r, r);
		l = t;
	}
	update(t);
}

void insert(pitem& t, pitem it)
{
	if (!t)
		t = it;
	else if (it->prior > t->prior)
	{
		split(t, it->key, it->l, it->r);
		t = it;
	}
	else
		insert((it->key < t->key) ? t->l : t->r, it);
	update(t);
}

void merge(pitem& t, pitem l, pitem r)
{
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
	{
		merge(l->r, l->r, r);
		t = l;
	}
	else
	{
		merge(r->l, l, r->l);
		t = r;
	}
	update(t);
}

int get(pitem t,int key)
{
	pitem l, r;
	split(t, key, l, r);
	int res = getVal(l);
	merge(t, l, r);
	return res;
}

pitem t, tx;


int n, x, mx, a[200005];


int main()
{
	t = tx = NULL;
	cin >> n >> x;
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
	{
		insert(tx, new item(get(tx, a[i] + x - 1) + 1, a[i] + x));
		insert(tx, new item(get(t, a[i] + x - 1) + 1, a[i] + x));
		insert(t, new item(get(t, a[i] - 1) + 1, a[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 << getVal(tx) << endl;

	return 0;
}


/*

3 1
1 1 3

*/

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:124: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: 17 / 17
• Subtask 7: 25 / 25