Submission #1030849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030849		pcc	Teams (IOI15_teams)	C++17	100 / 100	2272 ms	159172 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fs first
#define sc second
#define pii pair<int,int>

const int mxn = 5e5+10;
const int BK = 300;

pii arr[mxn];
int N;
int rt[mxn];

struct SEG{
#define mid ((l+r)>>1)
#define ls pl[now]
#define rs pr[now]
	const static int LEN = mxn*30;
	int pl[LEN],pr[LEN],seg[LEN];
	int ptr = 0;
	int newnode(int src = 0){
		ptr++;
		pl[ptr] = pl[src];
		pr[ptr] = pr[src];
		seg[ptr] = seg[src];
		assert(ptr<LEN);
		return ptr;
	}
	int modify(int now,int l,int r,int p){
		now = newnode(now);
		if(l == r){
			seg[now]++;
			return now;
		}
		if(mid>=p)ls = modify(ls,l,mid,p);
		else rs = modify(rs,mid+1,r,p);
		seg[now] = seg[ls]+seg[rs];
		return now;
	}
	int getval(int tl,int tr,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[tr]-seg[tl];
		if(mid>=e)return getval(pl[tl],pl[tr],l,mid,s,e);
		else if(mid<s)return getval(pr[tl],pr[tr],mid+1,r,s,e);
		else return getval(pl[tl],pl[tr],l,mid,s,e)+getval(pr[tl],pr[tr],mid+1,r,s,e);
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
vector<int> v[mxn];
vector<pii> kids;

void init(int NN, int A[], int B[]) {
	N = NN;
	for(int i = 0;i<N;i++)v[A[i]].push_back(B[i]);
	for(int i = 0;i<N;i++)kids.push_back(pii(A[i],B[i]));
	rt[0] = 0;
	for(int i = 1;i<=N;i++){
		rt[i] = rt[i-1];
		for(auto &j:v[i]){
			rt[i] = seg.modify(rt[i],1,N,j);
		}
	}
	sort(kids.begin(),kids.end());
	return;
}

namespace BRUTE{
	int GO(int M,int K[]){
		priority_queue<int,vector<int>,greater<int>> pq;
		sort(K,K+M);
		int ptr = 0;
		for(int i = 0;i<M;i++){
			while(ptr<kids.size()&&kids[ptr].fs<=K[i]){
				pq.push(kids[ptr].sc);
				ptr++;
			}
			while(!pq.empty()&&pq.top()<K[i])pq.pop();
			while(K[i]>0&&!pq.empty()){
				K[i]--;
				pq.pop();
			}
			if(K[i]>0)return 0;
		}
		return 1;
	}
}

namespace DP{
	ll dp[mxn];
	int GO(int M,int K[]){
		sort(K,K+M);
		for(int i = 0;i<M;i++){
			dp[i] = seg.getval(rt[0],rt[K[i]],1,N,K[i],N)-K[i];
			for(int j = 0;j<i;j++){
				ll tval = dp[j]+seg.getval(rt[K[j]],rt[K[i]],1,N,K[i],N)-K[i];
				dp[i] = min(dp[i],tval);
				if(dp[i]<0)return 0;
			}
			if(dp[i]<0)return 0;
		}
		return 1;
	}
}

int can(int M, int K[]) {
	if(M>=BK)return BRUTE::GO(M,K);
	else return DP::GO(M,K);
}

Compilation message (stderr)

teams.cpp: In function 'int BRUTE::GO(int, int*)':
teams.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    while(ptr<kids.size()&&kids[ptr].fs<=K[i]){
      |          ~~~^~~~~~~~~~~~

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