Submission #439916

#	Time	Username	Problem	Language	Result	Execution time	Memory
439916		AriaH	Jousting tournament (IOI12_tournament)	C++11	49 / 100	1089 ms	23576 KiB

tournament

/** vaziat sorati ghermeze **/

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, L[N], R[N], rmq[LOG][N];

vector < int > Q[N], id[N << 2], seg[N << 2];

void prep(int *arr)
{
	for(int i = 0; i < n - 1; i ++) rmq[0][i] = arr[i];
	for(int T = 1; T < LOG; T ++)
	{
		for(int i = 0; i < n - 1; i ++)
		{
			if((1 << T) + i > n + 1)
			{
				break;
			}
			rmq[T][i] = max(rmq[T - 1][i], rmq[T - 1][i + (1 << (T - 1))]);
		}
	}
}

void merge(int v)
{
	int sz1 = SZ(seg[v << 1]), sz2 = SZ(seg[v << 1 | 1]), i = 0, j = 0;
	id[v].push_back(0);
	while(i < sz1 || j < sz2)
	{
		if(j == sz2 || (i < sz1 && seg[v << 1][i] < seg[v << 1 | 1][j]))
		{
			id[v].push_back(id[v].back() + 1);
			seg[v].push_back(seg[v << 1][i ++]);
		}
		else
		{
			id[v].push_back(id[v].back());
			seg[v].push_back(seg[v << 1 | 1][j ++]);
		}
	}
}

void build(int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl == tr)
	{
		seg[v] = Q[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	merge(v);
}

int get(int l, int r, int I, int v = 1, int tl = 0, int tr = n - 1) /// [l, r] query onaii ke kamtar mosavi x an ro begu, I andise upper bound v e
{
	if(l > tr || r < tl || l > r) return 0;
	if(l <= tl && tr <= r)
	{
		return I;
	}
	int mid = (tl + tr) >> 1;
	return get(l, r, id[v][I], v << 1, tl, mid) + get(l, r, I - id[v][I], v << 1 | 1, mid + 1, tr);
}

inline int ask(int left, int right, int d, int up)
{
	if(left > right || d > up) return 0;
	return get(left, right, upper_bound(all(seg[1]), up) - seg[1].begin()) - get(left, right, upper_bound(all(seg[1]), d - 1) - seg[1].begin());
}

int GetBestPosition(int _n, int q, int x, int *p, int *l, int *r)
{
	n = _n;
	vector < pii > vec;
	for(int i = 0; i < n; i ++) vec.push_back(Mp(i, i));
	for(int i = 0; i < q; i ++)
	{
		int le = vec[l[i]].F, ri = vec[r[i]].S;
		L[i] = le, R[i] = ri;
		for(int j = l[i]; j <= r[i]; j ++)
		{
			vec.erase(vec.begin() + l[i]);
		}
		vec.insert(vec.begin() + l[i], {le, ri});
		Q[le].push_back(ri);
		///printf("query i = %d l = %d r = %d\n", i, le, ri);
	}
	build();
	prep(p);
	int tot = 0, ans = 0;
	for(int i = 0; i < n; i ++)
	{
		int d = i - 1, up = i;
		for(int T = LOG - 1; ~T; T --)
		{
			int pos = d - (1 << T) + 1;
			if(i && pos >= 0 && rmq[T][pos] < x)
			{
				d -= 1 << T;
			}
			pos = up + (1 << T) - 1;
			if(i != n - 1 && pos <= n - 2 && rmq[T][up] < x)
			{
				up += 1 << T;
			}
		}	
		d ++;
		int cu = ask(d, i, i, up);
		if(tot < cu)
		{
			tot = cu;
			ans = i;
		}
	}
	return ans;
}

/*int main()
{
	int _n, q, x, p[N], l[N], r[N];
	cin >> _n >> q >> x;
	for(int i = 0; i < _n - 1; i ++) cin >> p[i];
	for(int i = 0; i < q; i ++) cin >> l[i] >> r[i];
	cout << GetBestPosition(_n, q, x, p, l, r);
    return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/

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