Submission #68674

#	Time	Username	Problem	Language	Result	Execution time	Memory
68674		FLDutchman	Teams (IOI15_teams)	C++14	0 / 100	1136 ms	151520 KiB

teams

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

typedef int INT;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

struct segtree{
	vvi t;
	segtree(int n){
		t.resize(4*n);
	}

	void build(vi &arr, int lb, int rb, int n){
		if(rb-lb == 1) {
			t[n].pb(arr[lb]);
			return;
		}
		int mb = (lb+rb)/2;
		build(arr, lb, mb, n<<1);
		build(arr, mb, rb, n<<1|1);
		sort(&arr[lb], &arr[rb]);
		FOR(i, lb, rb) t[n].pb(arr[i]);
	}

	int qu(int l, int r, int c, int lb, int rb, int n){
		if(l == r) return 0;
		if(n!=0){
			//cout<<n<<endl;
			//cout << l << " " << r << endl;
		}
		if(l <= lb and rb <= r) return upper_bound(t[n].begin(), t[n].end(), c) - t[n].begin();
		int mb = (lb+rb)/2;
		int s = 0;
		if(l < mb) s += qu(l, r, c, lb, mb, n<<1);
		if(r > mb) s += qu(l, r, c, mb, rb, n<<1|1);
		return s;
	}
};

segtree t(0);
vii a, pre;
vi arr, prefix;
vi A, B;
int N;

void init(INT n, INT x[], INT y[]) {
	N = n;
	FOR(i, 0, N) A.pb(x[i]), B.pb(y[i]);
	t = segtree(N);
	a.resize(N);
	FOR(i, 0, N) a[i] = {B[i], A[i]};
	sort(a.begin(), a.end());
	arr.resize(N);
	FOR(i, 0, N) arr[i] = a[i].snd;
	t.build(arr, 0, N, 1);
	FOR(i, 0, N) pre.pb({A[i], -1});
	FOR(i, 0, N) pre.pb({B[i], 1});
	sort(pre.begin(), pre.end());
	prefix.resize(2*N+1, 0);
	FOR(i, 1, 2*N+1) prefix[i] = prefix[i-1] - pre[i-1].snd;

	//for(int k : prefix) cout << k << " ";
	//cout<<endl;
	//cout<<t.qu(1, 3, 2, 0, N, 1)<<endl;
}

INT can(INT M, INT K[]) {
	int T = upper_bound(pre.begin(), pre.end(), make_pair(K[0], 0)) - pre.begin();
	sort(K, K+M);
	int active = prefix[T], tbc = 0;
	FOR(i, 0, M-1){
		//cout << active << " " << tbc << endl;
		if(active < K[i]) return 0;
		active -= K[i];
		tbc += K[i];
		if(K[i] == K[i+1]) continue; 
		int nT = upper_bound(pre.begin(), pre.end(), make_pair(K[i+1], 0)) - pre.begin();
		int l = lower_bound(a.begin(), a.end(), make_pair(K[i], 0)) - a.begin();
		int r = lower_bound(a.begin(), a.end(), make_pair(K[i+1], 0)) - a.begin();
		tbc -= t.qu(l, r, K[i], 0, N, 1);
		if(tbc < 0) return 0;
		active = prefix[nT] - tbc;
		//cout<<nT<<endl;
		if(active < 0) return 0;
		//cout << active << " " << tbc << endl;
	}
	if(active < K[M-1]) return 0;
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int segtree::qu(int, int, int, int, int, int)':
teams.cpp:41:75: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   if(l <= lb and rb <= r) return upper_bound(t[n].begin(), t[n].end(), c) - t[n].begin();
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp: In function 'INT can(INT, INT*)':
teams.cpp:78:66: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
  int T = upper_bound(pre.begin(), pre.end(), make_pair(K[0], 0)) - pre.begin();
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:87:70: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int nT = upper_bound(pre.begin(), pre.end(), make_pair(K[i+1], 0)) - pre.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:88:63: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int l = lower_bound(a.begin(), a.end(), make_pair(K[i], 0)) - a.begin();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:89:65: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int r = lower_bound(a.begin(), a.end(), make_pair(K[i+1], 0)) - a.begin();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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