Submission #118162

#	Time	Username	Problem	Language	Result	Execution time	Memory
118162		davitmarg	Global Warming (CEOI18_glo)	C++17	Compilation error	0 ms	0 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

*//*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:173:8: error: redefinition of 'struct item'
 struct item
        ^~~~
glo.cpp:27:8: note: previous definition of 'struct item'
 struct item
        ^~~~
glo.cpp: In function 'int getVal(pitem)':
glo.cpp:190:5: error: redefinition of 'int getVal(pitem)'
 int getVal(pitem t)
     ^~~~~~
glo.cpp:44:5: note: 'int getVal(pitem)' previously defined here
 int getVal(pitem t)
     ^~~~~~
glo.cpp: In function 'void update(pitem)':
glo.cpp:195:6: error: redefinition of 'void update(pitem)'
 void update(pitem t)
      ^~~~~~
glo.cpp:49:6: note: 'void update(pitem)' previously defined here
 void update(pitem t)
      ^~~~~~
glo.cpp: In function 'void split(pitem, int, item*&, item*&)':
glo.cpp:202:6: error: redefinition of 'void split(pitem, int, item*&, item*&)'
 void split(pitem t, int key, pitem& l, pitem& r)
      ^~~~~
glo.cpp:56:6: note: 'void split(pitem, int, item*&, item*&)' previously defined here
 void split(pitem t, int key, pitem& l, pitem& r)
      ^~~~~
glo.cpp: In function 'void insert(item*&, pitem)':
glo.cpp:219:6: error: redefinition of 'void insert(item*&, pitem)'
 void insert(pitem& t, pitem it)
      ^~~~~~
glo.cpp:73:6: note: 'void insert(item*&, pitem)' previously defined here
 void insert(pitem& t, pitem it)
      ^~~~~~
glo.cpp: In function 'void merge(item*&, pitem, pitem)':
glo.cpp:233:6: error: redefinition of 'void merge(item*&, pitem, pitem)'
 void merge(pitem& t, pitem l, pitem r)
      ^~~~~
glo.cpp:87:6: note: 'void merge(item*&, pitem, pitem)' previously defined here
 void merge(pitem& t, pitem l, pitem r)
      ^~~~~
glo.cpp: In function 'int get(pitem, int)':
glo.cpp:250:5: error: redefinition of 'int get(pitem, int)'
 int get(pitem t,int key)
     ^~~
glo.cpp:104:5: note: 'int get(pitem, int)' previously defined here
 int get(pitem t,int key)
     ^~~
glo.cpp: At global scope:
glo.cpp:259:7: error: redefinition of 'item* t'
 pitem t, tx;
       ^
glo.cpp:113:7: note: 'item* t' previously declared here
 pitem t, tx;
       ^
glo.cpp:259:10: error: redefinition of 'item* tx'
 pitem t, tx;
          ^~
glo.cpp:113:10: note: 'item* tx' previously declared here
 pitem t, tx;
          ^~
glo.cpp:262:5: error: redefinition of 'int n'
 int n, x, mx, a[200005];
     ^
glo.cpp:116:5: note: 'int n' previously declared here
 int n, x, mx, a[200005];
     ^
glo.cpp:262:8: error: redefinition of 'int x'
 int n, x, mx, a[200005];
        ^
glo.cpp:116:8: note: 'int x' previously declared here
 int n, x, mx, a[200005];
        ^
glo.cpp:262:11: error: redefinition of 'int mx'
 int n, x, mx, a[200005];
           ^~
glo.cpp:116:11: note: 'int mx' previously declared here
 int n, x, mx, a[200005];
           ^~
glo.cpp:262:23: error: redefinition of 'int a [200005]'
 int n, x, mx, a[200005];
                       ^
glo.cpp:116:15: note: 'int a [200005]' previously declared here
 int n, x, mx, a[200005];
               ^
glo.cpp: In function 'int main()':
glo.cpp:265:5: error: redefinition of 'int main()'
 int main()
     ^~~~
glo.cpp:119:5: note: 'int main()' previously defined here
 int main()
     ^~~~
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);
   ~~~~~^~~~~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:270:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~