oj.uz

Submission #118158

# Submission time Handle Problem Language Result Execution time Memory
118158 2019-06-18T09:33:03 Z davitmarg Global Warming (CEOI18_glo) C++17
62 / 100
 902 ms 31284 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;

struct item
{
	int val, key, mxval;
	LL prior;
	item* l;
	item* r;
	item(int v = 0, int k = 0, LL p = 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;
	}
}

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

glo.cpp: In function 'int main()':
glo.cpp:123: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.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 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct

Subtask #3
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 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 3 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 29484 KB Output is correct
2 Correct 902 ms 30864 KB Output is correct
3 Correct 880 ms 30840 KB Output is correct
4 Correct 855 ms 30968 KB Output is correct
5 Correct 245 ms 30464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 7672 KB Output is correct
2 Correct 140 ms 8056 KB Output is correct
3 Correct 200 ms 7984 KB Output is correct
4 Correct 52 ms 7800 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 47 ms 7932 KB Output is correct
7 Correct 90 ms 8160 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 14872 KB Output is correct
2 Correct 368 ms 15864 KB Output is correct
3 Correct 901 ms 31284 KB Output is correct
4 Correct 231 ms 30456 KB Output is correct
5 Correct 105 ms 15352 KB Output is correct
6 Correct 161 ms 29012 KB Output is correct
7 Correct 226 ms 29748 KB Output is correct
8 Correct 193 ms 15864 KB Output is correct

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 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 3 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -