Submission #802976

#	Time	Username	Problem	Language	Result	Execution time	Memory
802976		happypotato	Teams (IOI15_teams)	C++17	0 / 100	256 ms	35268 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
int n;
vector<pii> v;
bool cmp(pii &lhs, pii &rhs) {
	if (lhs.ss != rhs.ss) return lhs.ss < rhs.ss;
	return lhs.ff < rhs.ff;
}
const int mxN = 1e5 + 1;
vector<int> seg[4 * mxN];
void merge(vector<int> &res, vector<int> &lhs, vector<int> &rhs) {
	int lptr = 0, rptr = 0;
	while (lptr < lhs.size() && rptr < rhs.size()) {
		if (lhs[lptr] < rhs[rptr]) {
			res.pb(lhs[lptr]); lptr++;
		} else {
			res.pb(rhs[rptr]); rptr++;
		}
	}
	while (lptr < lhs.size()) {
		res.pb(lhs[lptr]); lptr++;
	}
	while (rptr < rhs.size()) {
		res.pb(rhs[rptr]); rptr++;
	}
}
void build(int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = {v[l].ff};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	merge(seg[idx], seg[(idx << 1)], seg[(idx << 1) | 1]);
}
int query(int st, int tar, int nos, int l = 1, int r = n, int idx = 1) {
	// cerr << "query " << st << ' ' << tar << ' ' << nos << endl;
	if (l == r) {
		nos -= (seg[idx][0] <= tar);
		if (nos <= 0) return l;
		else return -nos;
	}
	int mid = (l + r) >> 1;
	if (st <= l) {
		int cnts;
		cnts = upper_bound(seg[idx].begin(), seg[idx].end(), tar) - seg[idx].begin();
		if (cnts < nos) return -(nos - cnts);
		cnts = upper_bound(seg[(idx << 1)].begin(), seg[(idx << 1)].end(), tar) - seg[(idx << 1)].begin();
		if (cnts >= nos) return query(st, tar, nos, l, mid, (idx << 1));
		else return query(st, tar, nos - cnts, mid + 1, r, (idx << 1) | 1);
	} else if (st <= mid) {
		int res = query(st, tar, nos, l, mid, (idx << 1));
		if (res > 0) return res;
		return query(st, tar, -res, mid + 1, r, (idx << 1) | 1);
	} else {
		return query(st, tar, nos, mid + 1, r, (idx << 1) | 1);
	}
}
void init(int N, int A[], int B[]) {
	n = N;
	v.resize(n + 1); v[0] = {0, 0};
	for (int i = 1; i <= n; i++) {
		v[i] = {A[i - 1], B[i - 1]};
	}
	sort(v.begin(), v.end(), cmp);
	build();
}

int can(int M, int K[]) {
	if (n == 1) return (K[0] == 1);
	int m = M;
	vector<int> tar(m);
	for (int i = 0; i < m; i++) tar[i] = K[i];
	sort(tar.begin(), tar.end());
	int pos = 1;
	for (int &need : tar) {
		if (pos > n) return 0;
		if (v[n].ss < need) return 0;
		int lb = 1, rb = n;
		while (lb < rb) {
			int mid = (lb + rb) >> 1;
			if (v[mid].ss >= need) rb = mid;
			else lb = mid + 1;
			// cerr << lb << ' ' << rb << ' ' << need << ' ' << v[1].ss << endl;
		}
		pos = max(pos, lb);
		// cerr << "lb " << lb << endl;
		int res = query(pos, need, need);
		// cerr << "res " << res << endl;
		if (res < 0) return 0;
		pos = res + 1;
	}
	return 1;
}
/*
fix pos (bounded by upper bound)
range descend find kth element >= tar (bounded by lower bound)
can be maintained by merge sort tree?
*/

Compilation message (stderr)

teams.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
teams.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  while (lptr < lhs.size() && rptr < rhs.size()) {
      |         ~~~~~^~~~~~~~~~~~
teams.cpp:19:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  while (lptr < lhs.size() && rptr < rhs.size()) {
      |                              ~~~~~^~~~~~~~~~~~
teams.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  while (lptr < lhs.size()) {
      |         ~~~~~^~~~~~~~~~~~
teams.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  while (rptr < rhs.size()) {
      |         ~~~~~^~~~~~~~~~~~
teams.cpp: In function 'int query(int, int, int, int, int, int)':
teams.cpp:53:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   53 |   cnts = upper_bound(seg[idx].begin(), seg[idx].end(), tar) - seg[idx].begin();
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:55:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   55 |   cnts = upper_bound(seg[(idx << 1)].begin(), seg[(idx << 1)].end(), tar) - seg[(idx << 1)].begin();
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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