Submission #742840

#	Time	Username	Problem	Language	Result	Execution time	Memory
742840		Abrar_Al_Samit	Teams (IOI15_teams)	C++17	0 / 100	480 ms	136520 KiB

teams

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

const int nax = 5e5 + 3;

struct BIT {
	int b[nax] = {0};

	int query(int p) {
		assert(p>0);
		int ret = 0;
		while(p>0) {
			ret += b[p];
			p -= p&-p;
		}
		return ret;
	}
	int query(int l, int r) {
		int ret = query(r);
		if(l>1) ret -= query(l-1);
		return ret;
	}
	void update(int p, int val) {
		assert(p>0);
		while(p<nax) {
			b[p] += val;
			p += p&-p;
		}
	}
} both, one;

vector<int>mst[nax * 4];
int n;
vector<int>atob[nax];

void build(int l, int r, int v) {
	if(l==r) {
		mst[v] = atob[l];
		return;
	}
	int mid = (l+r)/2;
	build(l, mid, v*2);
	build(mid+1, r, v*2+1);

	mst[v].resize(mst[v*2].size() + mst[v*2+1].size());
	merge(mst[v*2].begin(), mst[v*2].end(), mst[v*2+1].begin(), mst[v*2+1].end(), 
		mst[v].begin());

}
int query(int l, int r, int L, int R, int v) {
	if(l>=L && r<=R) {
		int ret = upper_bound(mst[v].begin(), mst[v].end(), R) - 
			mst[v].begin();

		return ret;
	}
	if(l>R || r<L) return 0;

	int mid = (l+r)/2;
	return query(l, mid, L, R, v*2) + query(mid+1, r, L, R, v*2+1);
}
void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0; i<N; ++i) {
		both.update(A[i], 1);
		both.update(B[i]+1, -1);
		one.update(B[i], 1);
	}
	for(int i=0; i<n; ++i) {
		atob[A[i]].push_back(B[i]);
	}
	for(int i=1; i<=n; ++i) {
		sort(atob[i].begin(), atob[i].end());
	}
	build(1, n, 1);
}

int can(int M, int K[]) {
	sort(K, K+M);
	int need[M];
	for(int i=0; i<M; ++i) {
		need[i] = K[i];
	}

	for(int i=0; i<M; ++i) {
		if(both.query(K[i])<need[i]) return 0;
		if(i==M-1) break;

		if(K[i]==K[i+1]) {
			need[i+1] += need[i];
			continue;
		}

		int ends_in_between = one.query(K[i], K[i+1]-1);
		if(K[i]+1!=K[i+1]) {
			ends_in_between -= query(1, n, K[i]+1, K[i+1]-1, 1);
		}
		if(need[i]>ends_in_between) {
			need[i+1] += need[i] - ends_in_between;
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:53:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   53 |   int ret = upper_bound(mst[v].begin(), mst[v].end(), R) -
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
   54 |    mst[v].begin();
      |    ~~~~~~~~~~~~~~

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