제출 #1156205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156205		benjaminj	Teams (IOI15_teams)	C++20	0 / 100	537 ms	145568 KiB

teams

#include "bits/stdc++.h"

using namespace std;
#define ll long long
#define pb push_back	
#define V vector
#define vi vector<int>
#define vl vector<long long>
#define vb vector<bool>
#define vs vector<string>
#define vd vector<double>
#define pi pair<int,int>
#define pd pair<double,double>
#define pl pair<long long, long long>
#define all(i) i.begin(),i.end()
#define REP(i,a,b) for(int i = a; i <= b; i++)
#define PER(i,a,b) for(int i = a; i >= b; i--)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i > b; i--)
#define indlb(v, x) (distance((v).begin(), lower_bound((v).begin(), (v).end(), (x))))
#define indub(v, x) (distance((v).begin(), upper_bound((v).begin(), (v).end(), (x))))
#define sz(i) (int) i.size()
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define currtime chrono::high_resolution_clock::now().time_since_epoch().count()

#define F first
#define S second
#define mp make_pair

template<typename T>
void printv(V<T> &x){
	for(T i : x)cout << i << " ";
	cout << "\n";
}
template<typename T>
void readv(V<T> &x){
	for(T &y : x)cin>>y;
}
inline int nxt(){
    int x; cin >> x; return x;
}

constexpr int MX_NODES = 3e7;
constexpr int RANGE_SZ = 5e5+5;
int tree[MX_NODES], l[MX_NODES], r[MX_NODES];
int timer = -1;
int build(int tl, int tr, const vector<int> &arr) {
    const int cur = ++timer;
    if (tl == tr) {
        tree[timer] = arr[tl];
        return cur;
    }

    int mid = (tl + tr) / 2;
    l[cur] = build(tl, mid, arr);
    r[cur] = build(mid+1, tr, arr);
    tree[cur] = tree[l[cur]] + tree[r[cur]];

    return cur;
}
int upd(int pos, int add, int v, int tl = 0, int tr = RANGE_SZ - 1) {
	const int cur = ++timer;
	if (tl == tr) {
		tree[cur] = add + tree[v];
		return cur;
	}

	l[cur] = l[v], r[cur] = r[v];

	const int mid = tl + (tr - tl) / 2;
	if (pos > mid) {
		r[cur] = upd(pos, add, r[v], mid + 1, tr);
	} else {
		l[cur] = upd(pos, add, l[v], tl, mid);
	}

	tree[cur] = tree[l[cur]] + tree[r[cur]];
	
	return cur;
}

int query(int v, int l1,int r1, int tl = 0, int tr = RANGE_SZ - 1) {
	if(l1<=tl && tr<=r1) return tree[v];
	const int mid = tl + (tr - tl) / 2;
	int sum = 0;
	if(mid>=l1) sum+= query(l[v], l1, r1, tl, mid);
	if(mid<r1)sum+= query(r[v],l1,r1,mid+1,tr);
	return sum;
}


int n;
vi roots;
V<pi> students;
void init(int n1, int *A, int *B){
	n = n1;
	students.resize(n);
	roots.resize(n+1);
	REP(i,0,n-1){
		students[i].F=A[i];
		students[i].S=B[i];
	}
	sort(all(students));
	vi v(RANGE_SZ+1);
	roots[0] = build(0, RANGE_SZ, v);
	REP(i,1,n){
		// cout << students[i-1].S << endl;
		roots[i] = upd(students[i-1].S,1,roots[i-1]);
	}
}

int can(int m, int *K){
	vi k(m);
	rep(i,0,m){
		k[i]=K[i];
	}
	sort(all(k));
	// printv(k);
	int maxp=0;
	vi big;
	int sum = 0;
	REP(i,0,m-1){
		sum+=k[i];
		// cout << i << " " << m << endl;
		if(i==m-1 || k[i]!=k[i+1]){
			int t = indlb(students,make_pair(k[i]+1,0));
			//check if i die
			// cout << i << " " << sum << " " << t << " " << maxp << " " <<query(roots[t],0,n) << endl;
			if(query(roots[t],0,n)-sum<maxp)return 0;
			//update minp
			// cout << k[i] << " " << query(roots.back(),0,k[i]) << endl;
			smax(maxp,query(roots.back(),0,k[i])-sum);
		}
	}
	return 1;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23