Submission #987308

#	Time	Username	Problem	Language	Result	Execution time	Memory
987308		vjudge1	Jousting tournament (IOI12_tournament)	C++17	100 / 100	321 ms	17364 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1<<17);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off<<1];
	bool rem[off << 1];
	int unit = 0;
	void pull(int idx){
		t[idx] = t[ls] + t[rs];
	}
	void update(int idx, int u){
		t[idx+=off] = u;
		while (idx/=2)
			pull(idx);
	}
	void push(int idx){
		if (!rem[idx]) return;
		t[idx] = 0;
		if (idx < off){
			rem[ls] = 1;
			rem[rs] = 1;
		}
		rem[idx] = 0;
	}
	void remRange(int l, int r, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return;
		if (l <= lo && hi <= r){
			rem[idx] = 1;
			push(idx);
			return ;
		}
		int mi = (lo+hi)>>1;
		remRange(l, r, ls, lo, mi); 
		remRange(l, r, rs, mi, hi);
		pull(idx);
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return unit;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return get(l, r, ls, lo, mi) + get(l, r, rs, mi, hi);
	}
	int find(int idx, int pos){
		push(idx);
		if (idx >= off) return idx - off;
		push(ls);
		if (t[ls] >= pos){
			return find(ls, pos);
		}
		return find(rs, pos - t[ls]);
	}
} seg;
struct range {
	int l, r;
	range(int L = off - 1, int R = off - 1) : l(L), r(R) {}
	friend bool operator <(range lhs, range rhs){
		if (lhs.l != rhs.l) return lhs.l > rhs.l; 
		return lhs.r < rhs.r;
	}// last cover most
	bool operator ==(range rhs){
		return l == rhs.l && r == rhs.r;
	}
	bool operator !=(range rhs){
		return l != rhs.l || r != rhs.r;
	}
};
struct sgt3 {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off<<1];
	int unit = 0;
	void pull(int idx){
		t[idx] = max(t[ls], t[rs]);
	}
	void update(int idx, int u){
		t[idx+=off] = u;
		while (idx/=2)
			pull(idx);
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return unit;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
	}
} seg3;
struct sgt2 {
#define ls (idx<<1)
#define rs (idx<<1|1)
	range t[off << 1];
	int cnt[off << 1];
	range unit = range(off - 1, off - 1);
	void pull(int idx){
		t[idx] = max(t[ls], t[rs]);
		cnt[idx] = cnt[ls] + cnt[rs];
	}
	void update(int idx, range u, int c = 1){
		t[idx+=off] = u;
		cnt[idx] = c;
		while (idx/=2)
			pull(idx);
	}
	range get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return unit;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
	}
	int getIdx(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return 0;
		if (l <= lo && hi <= r)
			return cnt[idx];
		int mi = (lo+hi)>>1;
		return getIdx(l, r, ls, lo, mi) + getIdx(l, r, rs, mi, hi);
	}
} seg2;

vector<int> add[MAXN], rem[MAXN];
int GetBestPosition(int n, int m, int R, int K[], int S[], int E[]){
	for (int i = 1; i <= n + 1; i++){
		seg.update(i, 1);
	}
	vector<range> ranges(m);
	for (int i = 0; i < m; i++){
		ranges[i] = range(seg.find(1, S[i] + 1), seg.find(1, E[i] + 2) - 1);
		seg.remRange(ranges[i].l + 1, ranges[i].r + 1);
	}
	sort(all(ranges));
	for (int i = 0; i < m; i++){
		add[ranges[i].l].pb(i);
		rem[ranges[i].r].pb(i);
		//cout << ranges[i].l << ' ' << ranges[i].r << endl;
	}
	vector<int> a(n + 1);
	a[1] = R;
	for (int i = 2; i <= n; i++){
		a[i] = K[i - 2];
	}
	for (int i = 1; i <= n; i++){
		seg3.update(i, a[i]);
	}
	pii ans = {-inf, -inf};
	//cout << endl;
	for (int i = 1; i <= n; i++){
		if (i != 1){
			swap(a[i], a[i - 1]);
			seg3.update(i, a[i]);
			seg3.update(i - 1, a[i - 1]);
		}
		for (auto u : add[i]){
			seg2.update(u, ranges[u], 1);
		}
		int lo = -1, hi = off - 1;
		while (hi - lo > 1){
			int mi = (lo + hi) / 2;
			range tm = seg2.get(0, mi + 1);
			if (seg3.get(tm.l, tm.r + 1) <= R){
				lo = mi;
			} else {
				hi = mi;
			}
		}
		ckmax(ans, {seg2.getIdx(0, hi), -(i - 1)});
		for (auto u : rem[i]){
			seg2.update(u, seg2.unit, 0);
		}
	}
	return -ans.S;
}

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