Submission #21804

#	Time	Username	Problem	Language	Result	Execution time	Memory
21804		sbansalcs	Teams (IOI15_teams)	C++14	21 / 100	4000 ms	364804 KiB

teams

#include "teams.h"
#include <stack>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e5+5;
#define right r
#define left l
#define mid (start+end)/2

struct node	{
	node *l,*r;
	int val;
	node()	{
		l=NULL,r=NULL,val=0;
	}
	node* build(int start, int end)	{
		val=0;
		if(start!=end)	{
			l=new node,r=new node,l=l->build(start,mid),r=r->build(mid+1,end);
		}
		return this;
	}

	int query(int start, int end, int a, int b)	{
		if(start>=a && end<=b)	return val;
		else if(start>b || end<a)	return 0;
		else	return l->query(start,mid,a,b)+r->query(mid+1,end,a,b);
	}

	node* update(int start, int end, int x, int v)	{
		node* f=new node;
		f->left=left;
		f->right=right;
		f->val=val+v;
		if(start==end)	{
			return f;
		}
		else if(x<=mid)	{
			f->left=left->update(start,mid,x,v);
		}
		else	{
			f->right=right->update(mid+1,end,x,v);
		}
		return f;
	}	

};
node* root[N];
int A[N],B[N];
int n;
int del[N];
int sz=0;
int dp[N];
void init(int _n, int a[], int b[]) {
	n=_n;
	vector<pair<int,int>> vt;

	for(int i=1;i<=n;i++)	{
		A[i]=a[i-1];
		B[i]=b[i-1];
		vt.push_back({A[i],B[i]});
	}
	sort(vt.begin(),vt.end());
	root[0]=new node;root[0]=root[0]->build(1,n);
	// cout<<"wow\n";
	int preve=0;
	for(int i=0;i<n;i++)	{
		while(preve+1<vt[i].first)	{
			root[preve+1]=root[preve];
			preve++;
			// cout<<"donel : "<<preve<<endl;
		}
		root[vt[i].first]=root[preve]->update(1,n,vt[i].second,1);
		assert(vt[i].first-preve<=1);
		preve=vt[i].first;

		// cout<<"done : "<<preve<<endl;
	}
		// cout<<"wow\n";

	for(int i=preve+1;i<=n;i++)	{
		root[i]=root[i-1];
		// cout<<"donez : "<<i<<endl;
	}
}

// int getUnder(int k, int y)	{

// 	int tot=0;
// 	for(int i=1;i<=n;i++)	{
// 		if(A[i]<=k && B[i]>=k)	tot++;
// 	}

// 	for(int i=sz;i>=1;i--)	{
		
// 	}
// }

// bool fx(int k)	{



// 	return 1;
// }

int getCount(int a, int b)	{

	int tot=0;
	for(int i=1;i<=n;i++)	{
		if(A[i]>a && A[i]<=b && B[i]>=b)	tot++;
	}
	// return tot;
	// cout<<"dot1 :"<<a<<"  ,  "<<b<<"\n";

	int h=root[b]->query(1,n,b,n)-root[max(0,a)]->query(1,n,b,n);
		// cout<<"dot2<< : "<<h<<"\n";

	assert(tot==h);
	return h;
}

int can(int M, int K[]) {
	sort(K,K+M);
	vector<pair<int,int>> vt;
	for(int i=0;i<M;i++)	{
		if(vt.size()==0 || vt[vt.size()-1].first!=K[i])	{
			vt.push_back({K[i],1});
		}
		else	{
			vt[vt.size()-1].second++;
		}
	}
	int n2 = vt.size();
	int h=sqrt(n);
	// assert(n2<=3*h);
	int mini=0;
	for(int i=0;i<n2;i++)	{
		dp[i]=getCount(0,vt[i].first)-vt[i].first*vt[i].second;
		for(int j=0;j<i;j++)	{
			dp[i]=min(dp[i],dp[j]-vt[i].first*vt[i].second+getCount(vt[j].first,vt[i].first));
		}
		if(dp[i]<0)	return 0;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:139:19: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int n2 = vt.size();
                   ^
teams.cpp:140:14: warning: conversion to 'int' from '__gnu_cxx::__enable_if<true, double>::__type {aka double}' may alter its value [-Wfloat-conversion]
  int h=sqrt(n);
              ^
teams.cpp:140:6: warning: unused variable 'h' [-Wunused-variable]
  int h=sqrt(n);
      ^
teams.cpp:142:6: warning: unused variable 'mini' [-Wunused-variable]
  int mini=0;
      ^

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