Submission #382821

#	Time	Username	Problem	Language	Result	Execution time	Memory
382821		aarr	Jousting tournament (IOI12_tournament)	C++14	0 / 100	79 ms	15420 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
 

const int N = 500 * 1000 + 5;

int L[N];
int R[N];
int c1[N], c2[N];
ordered_set s;
multiset <int> s2;
vector <int> vec[N];
int nxt[N];

int GetBestPosition(int n, int C, int rank, int *a, int *S, int *E) {
	for (int i = 0; i <= n; i++) {
		s.insert(i);
	}
	for (int i = 0; i < C; i++) {
		L[i] = *s.find_by_order(S[i]);
		R[i] = *s.find_by_order(E[i] + 1);
		vec[L[i]].push_back(R[i]);
	//	cout << "73 " << i << " " << L[i] << " " << R[i] << endl;
		for (int j = E[i]; j > S[i]; j--) {
		//	cout << "71 " << *s.find_by_order(j) << endl;
			s.erase(s.find_by_order(j));
		}
		
	}
	int ans = 0, cnt = 0;
	nxt[n - 1] = n;
	for (int i = n - 2; i >= 0; i--) {
		nxt[i] = nxt[i + 1];
		if (a[i] > rank) {
			nxt[i] = i;
		}
	//	cout << "72 " << i << " " << nxt[i] << endl;
	}
	for (int i = 0; i < n; i++) {
		for (auto x : vec[i]) {
		//	cnt++;
			if (nxt[i] + 1 >= x) {
				s2.insert(x);
			}
			
		}
		s2.erase(i);
	//	if (a[i] > rank) {
	//		while (s.size()) {
	//			s.erase(s.begin());
	//		}
	//	}
	//	cout << "74 " << i << " " << s2.size() << endl;
		ans = max(ans, (int) s2.size());
	}
	return ans;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:35:15: warning: unused variable 'cnt' [-Wunused-variable]
   35 |  int ans = 0, cnt = 0;
      |               ^~~

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