Submission #1131644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131644		ByeWorld	Jousting tournament (IOI12_tournament)	C++20	0 / 100	1 ms	2628 KiB

tournament

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+10;
const int MAXA = 1e6;
const int MOD = 1e9+7;
const int INF = 1e18+10;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a, b); }
void chmn(int &a, int b){ a = min(a, b); }

int n, c, r;
int s[MAXN], e[MAXN], k[MAXN], pr[MAXN];
vector <int> vec[MAXN];
set <int> ada;

struct seg {
	int st[2*MAXN];
	int que(int x){
		int te = 0;
		for(; x>=1; x-=(x&(-x))) te += st[x];
		return te;
	}
	void upd(int x, int p){
		for(; x<=2*MAXN-20; x+=(x&(-x)))
			st[x] += p;
	}
} A, B;
int que(int x){
	int l=1, r=n, cnt=0, mid=0;
	while(l<=r){
		mid = md;
		if(A.que(mid) >= x) cnt = mid, r=mid-1;
		else l=mid+1;
	}
	return cnt;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N, c = C, r = R; r++;
	for(int i=0; i<n-1; i++){
		K[i]++;
		if(K[i] <= r) k[i+1] = 0;
		else k[i+1] = 1; 
	}
	for(int i=1; i<=n-1; i++)
		pr[i] = pr[i-1]+k[i];
	for(int i=0; i<c; i++){
		s[i+1] = S[i]+1; e[i+1] = E[i]+1;
	}
	ada.insert(n+1);
	for(int i=1; i<=n; i++) A.upd(i, 1), ada.insert(i);
	for(int i=1; i<=c; i++){
		int sta = que(s[i]), en = que(e[i]);
		en = *ada.upper_bound(en);
		s[i] = sta; e[i] = en-1;
		vec[s[i]].pb(i); vec[e[i]+1].pb(-i);
		// cout << i << ' '<< s[i] << ' '<< e[i] << " pp\n";
		int te = *ada.upper_bound(sta);
		while(te != en){
			int te2 = *ada.upper_bound(te);
			A.upd(te, -1);
			ada.erase(te);
			te = te2;
		}
	}

	int mx = 0;
	set <int> gagal; // idx yg bikin gagal
	for(int i=1; i<=c; i++){
		for(auto id : vec[i]){
			int p = s[abs(id)], q = e[abs(id)]-1, val = pr[q]-pr[p-1];
			if(id < 0){
				B.upd(-id, -1);
				if(val != 0) gagal.erase(-id);
			} else {
				B.upd(id, 1);
				if(val != 0) gagal.insert(id);
			}
		}
		if(gagal.empty()) chmx(mx, B.que(c));
		else chmx(mx, B.que(*gagal.begin() - 1) );
	}
	return mx;
}

Compilation message (stderr)

tournament.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int INF = 1e18+10;
      |                 ~~~~^~~

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