Submission #288810

#	Time	Username	Problem	Language	Result	Execution time	Memory
288810		amoo_safar	Teams (IOI15_teams)	C++17	77 / 100	4054 ms	16144 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()
#define int unsigned int
using namespace std;

typedef pair<int, int> pii;

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

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(up + lazy - 1 < 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;
	}

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

void init(int32_t _n, int32_t A[], int32_t 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 ++;
	}

}

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

	if(sum > n) return 0;
	int sz, req, res;
	for(int gp = 0; gp < m; gp++){
		sz = K[gp];
		req = sz;
		while(gp + 1 < m && K[gp + 1] == sz){
			req += sz;
			gp ++;
		}
		
		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;
}

Compilation message (stderr)

teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:118:19: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int32_t' {aka 'int'} [-Wsign-compare]
  118 |  for(int i = 0; i < m; i++) sum += K[i];
      |                 ~~^~~
teams.cpp:122:21: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int32_t' {aka 'int'} [-Wsign-compare]
  122 |  for(int gp = 0; gp < m; gp++){
      |                  ~~~^~~
teams.cpp:125:16: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int32_t' {aka 'int'} [-Wsign-compare]
  125 |   while(gp + 1 < m && K[gp + 1] == sz){
      |         ~~~~~~~^~~
teams.cpp:125:33: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'unsigned int' [-Wsign-compare]
  125 |   while(gp + 1 < m && K[gp + 1] == sz){
      |                       ~~~~~~~~~~^~~~~

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