Submission #386722

#	Time	Username	Problem	Language	Result	Execution time	Memory
386722		ParsaAlizadeh	Teams (IOI15_teams)	C++17	0 / 100	1609 ms	409452 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

struct Node {
	int cnt;
	Node *lc, *rc;

	Node() : cnt(0), lc(this), rc(this) {}

	Node* add(int l, int r, int ind) {
		if (ind < l || r <= ind)
			return this;
		Node* cur = new Node();
		if (r - l == 1) {
			cur->cnt++;
			return cur;
		}
		int mid = (l + r) >> 1;
		cur->lc = lc->add(l, mid, ind);
		cur->rc = rc->add(mid, r, ind);
		cur->cnt = cur->lc->cnt + cur->rc->cnt;
		return cur; 
	}

	int get(Node* prv, int l, int r, int qr) {
		if (r <= qr)
			return cnt - prv->cnt;
		if (qr <= l)
			return 0;
		int mid = (l + r) >> 1;
		return lc->get(prv->lc, l, mid, qr) + rc->get(prv->rc, mid, r, qr);
	}

	int query(Node* prv, int l, int r, int t) {
		if (cnt - prv->cnt < t)
			return r;
		if (r - l == 1)
			return l;
		int mid = (l + r) >> 1;
		int lft = lc->cnt - prv->lc->cnt;
		if (lft >= t)
			return lc->query(prv->lc, l, mid, t);
		return rc->query(prv->rc, mid, r, t - lft);
	}

	Node* sub(Node* prv, int l, int r, int qr) {
		if (r <= qr)
			return this;
		if (qr <= l)
			return prv;
		int mid = (l + r) >> 1;
		Node* cur = new Node();
		cur->lc = lc->sub(prv->lc, l, mid, qr);
		cur->rc = rc->sub(prv->rc, mid, r, qr);
		cur->cnt = cur->lc->cnt + cur->rc->cnt;
		return cur;
	}
};

int n;
vector<Node*> root;
vector<int> R;

void init(int n, int *A, int *B) {
	::n = n;
	sort(A, A + n, [B] (int i, int j) {
		return B[i] < B[j];
	});
	sort(B, B + n);
	vector<int> L[n];
	for (int i = 0; i < n; i++)
		L[A[i] - 1].push_back(i);
	root.resize(n + 1);
	R.resize(n + 1);
	root[0] = new Node();
	for (int i = 0; i < n; i++) {
		root[i + 1] = root[i];
		for (int j : L[i]) {
			root[i + 1] = root[i + 1]->add(0, n, j);
		}
		R[i + 1] = lower_bound(B, B + n, i + 1) - B;
	}
}

int can(int M, int K[]) {
	sort(K, K + M);
	Node* cur = new Node();
	for (int i = 0; i < M; i++) {
		int t = root[K[i]]->get(cur, 0, n, R[K[i]]);
		int qr = root[K[i]]->query(cur, 0, n, t + K[i]);
		if (qr == n)
			return 0;
		cur = root[K[i]]->sub(cur, 0, n, qr + 1);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:65:32: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   65 | void init(int n, int *A, int *B) {
      |                                ^
teams.cpp:61:5: note: shadowed declaration is here
   61 | int n;
      |     ^
teams.cpp:82:43: warning: conversion from 'long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   82 |   R[i + 1] = lower_bound(B, B + n, i + 1) - B;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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