Submission #70749

#	Time	Username	Problem	Language	Result	Execution time	Memory
70749		Navick	Teams (IOI15_teams)	C++17	0 / 100	304 ms	20188 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

#define pb push_back
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;

const int maxN = 1e5 + 10, LOG = 19;

vector <int> qu[maxN], lefts;
int cnt[maxN], n, lf[maxN], rg[maxN];
int seg[LOG][maxN], perm[maxN];

bool cmp(int i, int j)
{
	return make_pair(lf[i], rg[i]) < make_pair(lf[j], rg[j]);
}

void build(int lg = 0, int s = 0, int e = n)
{
	if(e - s < 2)
	{
		int p = perm[s];
		seg[lg][s] = rg[p];
		return ;
	}
	int mid = (s + e)/2;
	build(lg + 1, s, mid);
	build(lg + 1, mid, e);

	merge(seg[lg + 1] + s, seg[lg + 1] + mid, seg[lg + 1] + mid, seg[lg + 1] + e, seg[lg] + s);

	return ;
}

int get(int lg, int L, int R, int ql, int qr, int s = 0, int e = n)
{
	if(L<=s && e<=R)
	{
		int idl = lower_bound(seg[lg] + s, seg[lg] + e, ql) - seg[lg];
		int idr = upper_bound(seg[lg] + s, seg[lg] + e, qr) - seg[lg];
		return idr - idl;
	}
	if(L>=e || s>=R) return 0;
	int mid = (s + e)/2;
	return get(lg + 1, L, R, ql, qr, s, mid) + get(lg + 1, L, R, ql, qr, mid, e);
}

void init(int N, int A[], int B[]) {
	n = N;
	for (int i=0; i<n; i++) lf[i] = A[i], rg[i] = B[i], lefts.pb(lf[i]);
	sort(lefts.begin(), lefts.end());

	for (int i=0; i<n; i++) perm[i] = i;
	sort(perm, perm + n, cmp);

	build();
}

vector <int> vc;

int can(int m, int k[]) {

	//for (auto x : lefts) cout << x << ' '; cout << endl;

	vc.clear();
	for (int i=0; i<m; i++) vc.pb(k[i]), cnt[k[i]] ++;

	sort(vc.begin(), vc.end());
	vc.resize(unique(vc.begin(), vc.end()) - vc.begin());

	int sz = (int) vc.size(), last = 0;
	ll s = 0, p = 0;

	for (int i=0; i<sz; i++)
	{
		int x = vc[i];

		int pl = upper_bound(lefts.begin(), lefts.end(), last) - lefts.begin();
		int pr = lower_bound(lefts.begin(), lefts.end(), x + 1) - lefts.begin();
		
		int g1 = get(0, pl, pr, x , n);

		pl = 0;
		pr = lower_bound(lefts.begin(), lefts.end(), last + 1) - lefts.begin();

		int g2 = get(0, pl, pr, last, x - 1);
		
		if(p >= g2) p -= g2;
		else s -= g2 - p, p = 0;

		s += g1;

		if(s < 1LL * cnt[x] * x) {
			for (int j=0; j<m; j++) cnt[k[j]] --;
			return 0;
		}

		s -= 1LL * cnt[x] * x;
		p += 1LL * cnt[x] * x;
	
		last = vc[i];

		//cout << i << " --> " << s << ',' << p << endl;
		//cout << cnt[i] << endl;
	}

	for (int i=0; i<m; i++) cnt[k[i]] --;

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int get(int, int, int, int, int, int, int)':
teams.cpp:44:55: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int idl = lower_bound(seg[lg] + s, seg[lg] + e, ql) - seg[lg];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp:45:55: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int idr = upper_bound(seg[lg] + s, seg[lg] + e, qr) - seg[lg];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:83:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int pl = upper_bound(lefts.begin(), lefts.end(), last) - lefts.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:84:59: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int pr = lower_bound(lefts.begin(), lefts.end(), x + 1) - lefts.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:89:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   pr = lower_bound(lefts.begin(), lefts.end(), last + 1) - lefts.begin();
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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