Submission #51279

#	Time	Username	Problem	Language	Result	Execution time	Memory
51279		Mamnoon_Siam	Jousting tournament (IOI12_tournament)	C++17	100 / 100	322 ms	28880 KiB

tournament

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

typedef pair<int, int> ii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

struct MaxSegmentTree {
	vector<int> t;
	MaxSegmentTree() {}
	MaxSegmentTree(vector<int> &vec) {
		t.resize(vec.size() * 2);
		for(int i = 0; i < vec.size(); i++) {
			t[i + vec.size()] = vec[i];
		}
		for(int i = vec.size() - 1; i; i--) {
			t[i] = max(t[i << 1], t[i << 1 | 1]);
		}
	}
	int get_max(int l, int r) { r++; int ret = -1;
		for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
			if(l & 1) ret = max(ret, t[l++]);
			if(r & 1) ret = max(ret, t[--r]);
		} return ret;
	}
};

struct IntervalTree {
	vector<vector<int>> t;
	IntervalTree() {}
	IntervalTree(int _N) {
		t.resize(_N << 1);
	}
	void AddInterval(int l, int r, int val) { r++;
		for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
			if(l & 1) t[l++].push_back(val);
			if(r & 1) t[--r].push_back(val);
		}
	}
	void sort() {
		for(int i = 0; i < t.size(); i++) {
			std::sort(all(t[i]));
		}
	}
	int count(int p, int val) { int ret = 0;
		for(p += (t.size() >> 1); p > 0; p >>= 1) ret += lower_bound(all(t[p]), val) - t[p].begin();
		return ret;
	}
};

vector<int> K, S, E;
int N, C, R;
vector<ii> intervals;
vector<int> val;

int get_max(int l, int r) {
	int mx = -1;
	for(int i = l; i <= r; i++) {
		mx = max(mx, K[i]);
	} return mx;
}

int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E) {
	N = _N, C = _C, R = _R;
	K.assign(N - 1, 0), S.assign(C, 0), E.assign(C, 0);
	for(int i = 0; i < N - 1; i++) K[i] = _K[i];
	for(int i = 0; i < C; i++) S[i] = _S[i], E[i] = _E[i];
	ordered_set os;
	for(int i = 0; i < N; i++) {
		os.insert(ii(i, i));
	}
	for(int i = 0; i < C; i++) {
		vector<ii> dlt;
		auto l_it = os.find_by_order(S[i]);
		auto r_it = os.find_by_order(E[i]);
		ii in = ii(l_it -> first, r_it -> second);
		r_it++;
		for(auto it = l_it; it != r_it; it++) dlt.push_back(*it);
		for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
		os.insert(in);
		intervals.push_back(in);
	} val.resize(intervals.size());

	MaxSegmentTree mst(K);

	for(int i = 0; i < intervals.size(); i++) {
		val[i] = mst.get_max(intervals[i].first, intervals[i].second - 1);
	}

	IntervalTree Itree(N);

	for(int i = 0; i < intervals.size(); i++) {
		Itree.AddInterval(intervals[i].first, intervals[i].second, val[i]);
	}
	Itree.sort();

	int mx = -1, id = -1;
	for(int i = 0; i < N; i++) {
		int c = Itree.count(i, R);
		if(c > mx) {
			mx = c;
			id = i;
		}
	}
	return id;
}

Compilation message (stderr)

tournament.cpp: In function 'int myrand(int, int)':
tournament.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
tournament.cpp:22:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
tournament.cpp: In constructor 'MaxSegmentTree::MaxSegmentTree(std::vector<int>&)':
tournament.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
tournament.cpp: In member function 'void IntervalTree::sort()':
tournament.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < t.size(); i++) {
                  ~~^~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
                  ~~^~~~~~~~~~~~
tournament.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < intervals.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~
tournament.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < intervals.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~

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