Submission #442308

#	Time	Username	Problem	Language	Result	Execution time	Memory
442308		AriaH	Jousting tournament (IOI12_tournament)	C++11	0 / 100	82 ms	32288 KiB

tournament

/** vaziat sorati ghermeze **/
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#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 = 18;
 
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];
 
int 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) 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 fen[N];
 
void add(int i, int x)
{
	for(; i < N; i += i & -i) fen[i] += x;
}
 
int ask(int x) /// x omin element left esh
{
	int p = 0, cnt = 0;
	for(int T = LOG - 1; ~T; T --)
	{
		int now = p + (1 << T);
		if(now < N && cnt + fen[now] + cnt < x)
		{
			p = now;
			cnt += fen[now];
		}
	}
	return p + 1;
}
 
int GetBestPosition(int _n, int q, int x, int *p, int *l, int *r)
{
	n = _n;
	vector < pii > vec;
	for(int i = 1; i <= n + 3; i ++) add(i, 1);
	for(int i = 0; i < q; i ++)
	{
		int le = ask(l[i] + 1) - 1, ri = ask(r[i] + 2) - 2;
		L[i] = le, R[i] = ri;
		for(int j = l[i] + 1; j <= r[i]; j ++)
		{
			add(ask(j + 1), -1);
		}
		Q[le].push_back(ri);
		///printf("query i = %d l = %d r = %d\n", i, L[i], R[i]);
	}
	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: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51