제출 #288792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288792		amoo_safar	팀들 (IOI15_teams)	C++17	77 / 100	4099 ms	16208 KiB

teams

#include "teams.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 5e5 + 10;
const int Sq = 700;

int n, L[N], R[N], mk[N];

struct Block {
	int l, r, lazy;
	int ord[Sq], sz_ord;
	int lord[Sq], sz_lord;
	//vector<int> ord, lord;
	bool Marked;
	void Build(int _l, int _r){
		l = _l; r = _r; lazy = 0; Marked = false;
		sz_ord = r - l; sz_lord = r - l;
		//ord.resize(r - l);
		iota(ord, ord + sz_ord, l);
		sort(ord, ord + sz_ord, [&](int i, int j){
			return L[i] < L[j];
		});
		for(int i = 0; i < sz_ord; i++)
			lord[i] = ord[i];
	}
	inline void Rebuild(){
		//ord.clear();
		sz_ord = 0;
		for(int i = 0; i < sz_lord; i++){
			if(!mk[lord[i]])
				ord[sz_ord ++] = lord[i];
		}
	}
	inline void Relax(){
		if(!lazy) return ;
		Marked = true;
		for(int i = 0; i < lazy; i++) mk[ord[i]] = 1; 
		lazy = 0;
		//Rebuild();
	}
	inline int Count(int x, int up){
		if(lazy - 1 + up < sz_ord && L[ord[lazy - 1 + up]] <= x) return up;

		int Lb = lazy - 1, Rb = sz_ord;
		int mid;
		while(Lb + 1 < Rb){
			mid = (Lb + Rb) >> 1;
			if(L[ord[mid]] <= x) Lb = mid;
			else Rb = mid;
		}
		return Rb - lazy;
	}
	inline void Pick(int cnt){
		lazy += cnt;
	}
	inline int Solve(int cnt, int sz){
		Relax();
		for(int i = l; i < r; i++){
			if(!mk[i] && L[i] <= sz && sz <= R[i]){
				cnt --;
				mk[i] = 1;
				Marked = true;
				if(cnt == 0) break;
			}
		}
		Rebuild();
		return cnt;
	}

	void Reset(){
		lazy = 0;
		if(!Marked) return ;
		Marked = false;
		for(int i = l; i < r; i++) mk[i] = 0;
		Rebuild();
	}
};
Block bl[N / Sq + 10];
int k;

void init(int _n, int A[], int B[]) {
	n = _n;
	vector<int> I(n);
	iota(all(I), 0);
	sort(all(I), [&](int i, int j){
		if(B[i] != B[j]) return B[i] < B[j];
		return A[i] < A[j];
	});
	for(int i = 0; i < n; i++) L[i] = A[I[i]];
	for(int i = 0; i < n; i++) R[i] = B[I[i]];

	k = 0;
	for(int i = 0; i < n; i += Sq){
		bl[i / Sq].Build(i, min(i + Sq, n));
		k ++;
	}

}

int can(int m, int K[]){
	sort(K, K + m);
	for(int i = 0; i < k; i++) bl[i].Reset();

	int sz, req, res;
	for(int gp = 0; gp < m; gp++){
		sz = K[gp];
		req = sz;
		for(int i = 0; i < k; i++){
			if(req == 0) break;
			if(R[bl[i].r - 1] < sz) continue;
			if(R[bl[i].l] < sz){
				req = bl[i].Solve(req, sz);
				continue;
			}
			res = bl[i].Count(sz, req + 1);
			if(res <= req){
				req -= res;
				bl[i].Pick(res);
			} else {
				req = bl[i].Solve(req, sz);
				assert(req == 0);
			}
		}

		if(req)
			return 0;
	}
	return 1;
}

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