Submission #363317

#	Time	Username	Problem	Language	Result	Execution time	Memory
363317		NachoLibre	Jousting tournament (IOI12_tournament)	C++17	100 / 100	277 ms	24300 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
// #include ".h"
#else
#endif

struct sws {
	sws *l, *r;
	int x;
	sws() {
		l = r = NULL;
		x = 0;
	}

	void P() {
		if(l == NULL) l = new sws();
		if(r == NULL) r = new sws();
	}

	void Px() {
		P(); x = max(l->x, r->x);
	}

	void Ps() {
		P(); x = l->x + r->x;
	}
};
struct dmtree {
	sws *rt;
	const int n;
	dmtree(int _n) : n(_n), rt(NULL) {};

	static void _set(int l, int r, sws *&t, int si, int vl) {
		if(t == NULL) t = new sws();
		if(l == r) {
			t->x = vl;
			return;
		}
		int m = l + r >> 1;
		if(m >= si) _set(l, m, t->l, si, vl);
		else _set(m + 1, r, t->r, si, vl);
	}

	static int _get(int l, int r, sws *&t, int si) {
		assert(t != NULL);
		if(l == r) return t->x;
		int m = l + r >> 1;
		if(m >= si) return _get(l, m, t->l, si);
		else return _get(m + 1, r, t->r, si);
	}

	void set(int i, int x) {
		_set(0, n - 1, rt, i, x);
	}

	int get(int i) {
		return _get(0, n - 1, rt, i);
	}
};
struct mxtree {
	sws *rt;
	const int n;

	mxtree(int _n) : n(_n), rt(NULL) {}

	static void _set(int l, int r, sws *&t, int si, int vl) {
		if(t == NULL) t = new sws();
		if(l == r) {
			t->x = vl;
			return;
		}
		int m = l + r >> 1;
		if(m >= si) _set(l, m, t->l, si, vl);
		else _set(m + 1, r, t->r, si, vl);
		t->Px();
	}

	static int _get(int l, int r, sws *&t, int sl, int sr) {
		if(l > sr || r < sl || t == NULL) return 0;
		if(l >= sl && r <= sr) return t->x;
		int m = l + r >> 1;
		return max(_get(l, m, t->l, sl, sr), _get(m + 1, r, t->r, sl, sr));
	}

	void set(int i, int x) {
		_set(0, n - 1, rt, i, x);
	}

	void erase(int i) {
		set(i, 0);
	}

	int operator()(int l, int r) {
		return _get(0, n - 1, rt, l, r);
	}
};
struct sptree {
	dmtree dt;
	sws *rt;
	const int n;
	sptree(int _n) : n(_n), rt(NULL), dt(dmtree(n)) {};

	static void _set(int l, int r, sws *&t, int si, int vl) {
		if(t == NULL) t = new sws();
		if(l == r) {
			t->x = vl;
			return;
		}
		int m = l + r >> 1;
		if(m >= si) _set(l, m, t->l, si, vl);
		else _set(m + 1, r, t->r, si, vl);
		t->Ps();
	}

	static int _get(int l, int r, sws *&t, int x) {
		if(l == r) return l;
		t->P();
		int m = l + r >> 1;
		int cl = t->l->x;
		if(cl >= x) return _get(l, m, t->l, x);
		else return _get(m + 1, r, t->r, x - cl);
	}

	int get(int x) {
		++x;
		if(rt == NULL || rt->x < x) return -1;
		return _get(0, n - 1, rt, x);
	}

	void set(int i, int x) {
		_set(0, n - 1, rt, i, 1);
		dt.set(i, x);
	}

	void remove(int i) {
		_set(0, n - 1, rt, i, 0);
		dt.set(i, 0);
	}

	int operator[](int i) {
		return dt.get(i);
	}
};

const int N = 100005;
int up[N * 2], sg[N * 2][2];

int GetBestPosition(int n, int c, int r, int k[], int s[], int e[]) {
	if(n == 1) return 0;
	for(int i = 0; i < n + c; ++i) up[i] = -1;
	//  //  //  //  //  //  //  //
	sptree spt(n);
	mxtree mxt(n);
	for(int i = n - 1; i >= 1; --i) {
		k[i] = k[i - 1];
		mxt.set(i, k[i]);
	}
	mxt.set(0, r);
	k[0] = r;
	for(int i = 0; i < n; ++i) {
		sg[i][0] = sg[i][1] = i;
		spt.set(i, i);
	}
	for(int i = 0; i < c; ++i) {
		for(int j = 0; j <= e[i] - s[i]; ++j) {
			int x = spt.get(s[i]);
			int y = spt[x];
			up[y] = n + i;
			spt.remove(x);
			if(j == 0) {
				sg[n + i][0] = sg[y][0];
			} else if(j == e[i] - s[i]) {
				sg[n + i][1] = sg[y][1];
			}
		}
		spt.set(sg[n + i][0], n + i);
	}
	int ap = 0, fp = 0, dr = 0;
	for(int i = 0; i < n; ++i) {
		{
			int x = up[i];
			while(sg[x][0] == i) {
				// cout << x << " " << mxt(sg[x][0], sg[x][1]) << " " << k[i] << endl;
				if(mxt(sg[x][0], sg[x][1]) == k[i]) {
					++ap;
				}
				x = up[x];
				if(x == -1) break;
			}
		}
		// cout << ap << endl;
		if(ap > fp) {
			fp = ap;
			dr = i;
		}
		if(i < n - 1) {
			int x = up[i];
			while(sg[x][1] == i) {
				if(mxt(sg[x][0], sg[x][1]) == k[i]) {
					--ap;
				} else {
					break;
				}
				x = up[x];
				if(x == -1) break;
			}
			mxt.set(i + 1, k[i]);
			mxt.set(i, k[i + 1]);
			swap(k[i], k[i + 1]);
		}
	}
	#ifdef wambulex
	for(int i = 0; i < n; ++i) {
		int x = i;
		while(x != -1) {
			cout << x << " ";
			x = up[x];
		}
		cout << endl;
	}
	#endif
	return dr;
}

#ifdef wambule
int n = 5;
int k[] = {1, 0, 2, 4};
int r = 3;
int c = 3;
int s[] = {1, 0, 0};
int e[] = {3, 1, 1};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << GetBestPosition(n, c, r, k, s, e) << endl;
	return 0;
}
#endif

Compilation message (stderr)

tournament.cpp: In constructor 'dmtree::dmtree(int)':
tournament.cpp:33:12: warning: 'dmtree::n' will be initialized after [-Wreorder]
   33 |  const int n;
      |            ^
tournament.cpp:32:7: warning:   'sws* dmtree::rt' [-Wreorder]
   32 |  sws *rt;
      |       ^~
tournament.cpp:34:2: warning:   when initialized here [-Wreorder]
   34 |  dmtree(int _n) : n(_n), rt(NULL) {};
      |  ^~~~~~
tournament.cpp: In static member function 'static void dmtree::_set(int, int, sws*&, int, int)':
tournament.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In static member function 'static int dmtree::_get(int, int, sws*&, int)':
tournament.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In constructor 'mxtree::mxtree(int)':
tournament.cpp:65:12: warning: 'mxtree::n' will be initialized after [-Wreorder]
   65 |  const int n;
      |            ^
tournament.cpp:64:7: warning:   'sws* mxtree::rt' [-Wreorder]
   64 |  sws *rt;
      |       ^~
tournament.cpp:67:2: warning:   when initialized here [-Wreorder]
   67 |  mxtree(int _n) : n(_n), rt(NULL) {}
      |  ^~~~~~
tournament.cpp: In static member function 'static void mxtree::_set(int, int, sws*&, int, int)':
tournament.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In static member function 'static int mxtree::_get(int, int, sws*&, int, int)':
tournament.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In constructor 'sptree::sptree(int)':
tournament.cpp:103:12: warning: 'sptree::n' will be initialized after [-Wreorder]
  103 |  const int n;
      |            ^
tournament.cpp:102:7: warning:   'sws* sptree::rt' [-Wreorder]
  102 |  sws *rt;
      |       ^~
tournament.cpp:104:2: warning:   when initialized here [-Wreorder]
  104 |  sptree(int _n) : n(_n), rt(NULL), dt(dmtree(n)) {};
      |  ^~~~~~
tournament.cpp:102:7: warning: 'sptree::rt' will be initialized after [-Wreorder]
  102 |  sws *rt;
      |       ^~
tournament.cpp:101:9: warning:   'dmtree sptree::dt' [-Wreorder]
  101 |  dmtree dt;
      |         ^~
tournament.cpp:104:2: warning:   when initialized here [-Wreorder]
  104 |  sptree(int _n) : n(_n), rt(NULL), dt(dmtree(n)) {};
      |  ^~~~~~
tournament.cpp: In static member function 'static void sptree::_set(int, int, sws*&, int, int)':
tournament.cpp:112:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In static member function 'static int sptree::_get(int, int, sws*&, int)':
tournament.cpp:121:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |   int m = l + r >> 1;
      |           ~~^~~
tournament.cpp: In constructor 'sptree::sptree(int)':
tournament.cpp:104:46: warning: '*<unknown>.sptree::n' is used uninitialized in this function [-Wuninitialized]
  104 |  sptree(int _n) : n(_n), rt(NULL), dt(dmtree(n)) {};
      |                                              ^

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51