Submission #288768

#	Time	Username	Problem	Language	Result	Execution time	Memory
288768		amoo_safar	Teams (IOI15_teams)	C++17	77 / 100	4069 ms	23760 KiB

teams

#include "teams.h"

#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 = 600;

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;
		ord.resize(r - l);
		iota(all(ord), l);
		sort(all(ord), [&](int i, int j){
			return L[i] < L[j];
		});
		lord = ord;
	}
	inline void Rebuild(){
		ord.clear();
		for(auto x : lord){
			if(!mk[x])
				ord.pb(x);
		}
	}
	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 Lb = lazy - 1, Rb = ord.size();
		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);
			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;
}

Compilation message (stderr)

teams.cpp: In member function 'int Block::Count(int)':
teams.cpp:46:35: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   46 |   int Lb = lazy - 1, Rb = ord.size();
      |                           ~~~~~~~~^~

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