제출 #1156400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156400		benjaminj	Teams (IOI15_teams)	C++20	0 / 100	991 ms	171112 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>r1)return 0;
	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;
}

bool cmp(const vi &a, const vi &b){
	if(a[1]!=b[1])return a[1]<b[1];
	return a[0]<b[0];
}

int n;
vi roots;
V<vi> students;
vi students2;
void init(int n1, int *A, int *B){
	n = n1;
	students = V<vi>(n,vi(3));
	roots.resize(n+1);
	REP(i,0,n-1){
		students[i][0]=A[i];
		students[i][1]=B[i];
	}
	sort(all(students),cmp);
	REP(i,0,n-1)students[i][2]=i;
	sort(all(students));
	REP(i,0,n-1)students2.pb(students[i][0]);
	vi v(RANGE_SZ+1);
	roots[0] = build(0, RANGE_SZ, v);
	REP(i,1,n){
		roots[i] = upd(students[i-1][2],1,roots[i-1]);
	}
}

int walk(int k, int u, int v, int tl = 0, int tr = RANGE_SZ-1){
	if(tl==tr) return tl;
	int mid = tl+(tr-tl)/2;
	int nxt = tree[l[v]]-tree[l[u]];
	if(nxt>=k){
		return walk(k,l[u],l[v],tl,mid);
	}
	return walk(k-nxt,r[u],r[v],mid+1,tr);
}

int can(int m, int *K){
	map<int,int> counts;
	rep(i,0,m){
		counts[K[i]]+=K[i];
	}
	V<vi> blocks;
	blocks.reserve(m+2);
	blocks.pb({-1,n,n});
	blocks.pb({0,0,n});
	// cout << "CASE\n";
	for(auto p : counts){
		int k = p.F;
		int t = indlb(students2,k+1);
		int count = p.S;
		// cout << k << " " << count << endl;
		while(count){
			// cout << "BLOCKS\n";
			// for(vi block : blocks){
			// 	printv(block);
			// }
			if(sz(blocks)==1)return 0;
			int x = blocks.back()[0];
			int y1 = blocks.back()[1];
			int y2 = blocks.back()[2];
			blocks.pop_back();
			int t2 = indlb(students2,x);
			int a = query(roots[t],y1,y2-1)-query(roots[t2],y1,y2-1);
			// cout << "xy " << x << " " << y1 << " " << y2 << " " << a << " " << count << endl;
			if(a<=count){
				count-=a;
			}
			else{
				int target = count+query(roots[t],0,y1-1)-query(roots[t2],0,y1-1);
				int y3 = walk(target,roots[t2],roots[t])+1;
				assert(y3 > y1 && y3 <= y2);
				// cout << y3 << endl;
				blocks.pb({x,y3,blocks.back()[1]});
				break;
			}
		}
		blocks.pb({t+1,0,blocks.back()[1]});
	}
	return 1;
}

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