Submission #802996

#	Time	Username	Problem	Language	Result	Execution time	Memory
802996		happypotato	Teams (IOI15_teams)	C++17	0 / 100	212 ms	35244 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;
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].ss};
		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 (r < st) return -nos;
	else if (st <= l) {
		int cnts;
		cnts = seg[idx].end() - lower_bound(seg[idx].begin(), seg[idx].end(), tar);
		if (cnts < nos) return -(nos - cnts);
		cnts = seg[(idx << 1)].end() - lower_bound(seg[(idx << 1)].begin(), seg[(idx << 1)].end(), tar);
		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() + 1, v.end());
	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 = 0;
	for (int &need : tar) {
		pos++;
		if (pos > n) return 0;
		if (v[pos].ff > need) return 0;
		int lb = 1, rb = n;
		while (lb < rb) {
			int mid = (lb + rb + 1) >> 1;
			if (v[mid].ff <= need) lb = mid;
			else rb = mid - 1;
			// cerr << lb << ' ' << rb << ' ' << need << ' ' << v[1].ss << endl;
		}
		// cerr << "lb " << lb << endl;
		int res = query(pos, need, need);
		// cerr << "res " << res << endl;
		if (res > lb || res < 0) return 0;
		pos = res;
	}
	return (pos <= n);
}
/*
fix pos (bounded by upper bound)
range descend find kth element >= tar (bounded by lower bound)
can be maintained by merge sort tree?

end of virtual
lemme upsolve this subtask first
*/

Compilation message (stderr)

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

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