oj.uz

Submission #21805

# Submission time Handle Problem Language Result Execution time Memory
21805 2017-04-25T21:43:50 Z sbansalcs Teams (IOI15_teams) C++14
34 / 100
 4000 ms 366908 KB 

#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13780 KB Output is correct
2 Correct 0 ms 13780 KB Output is correct
3 Correct 0 ms 13780 KB Output is correct
4 Correct 0 ms 13780 KB Output is correct
5 Correct 0 ms 13780 KB Output is correct
6 Correct 0 ms 13928 KB Output is correct
7 Correct 0 ms 13780 KB Output is correct
8 Correct 0 ms 13780 KB Output is correct
9 Correct 0 ms 13780 KB Output is correct
10 Correct 0 ms 13780 KB Output is correct
11 Correct 0 ms 13780 KB Output is correct
12 Correct 0 ms 13780 KB Output is correct
13 Correct 0 ms 13780 KB Output is correct
14 Correct 0 ms 13780 KB Output is correct
15 Correct 0 ms 13780 KB Output is correct
16 Correct 0 ms 13780 KB Output is correct
17 Correct 0 ms 13780 KB Output is correct
18 Correct 0 ms 13780 KB Output is correct
19 Correct 0 ms 13780 KB Output is correct
20 Correct 0 ms 13780 KB Output is correct
21 Correct 0 ms 13780 KB Output is correct
22 Correct 0 ms 13780 KB Output is correct
23 Correct 0 ms 13780 KB Output is correct
24 Correct 0 ms 13780 KB Output is correct
25 Correct 0 ms 13780 KB Output is correct
26 Correct 0 ms 13780 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 77180 KB Output is correct
2 Correct 146 ms 77180 KB Output is correct
3 Correct 133 ms 77180 KB Output is correct
4 Correct 123 ms 77180 KB Output is correct
5 Correct 109 ms 77180 KB Output is correct
6 Correct 93 ms 77180 KB Output is correct
7 Correct 73 ms 77180 KB Output is correct
8 Correct 66 ms 77180 KB Output is correct
9 Correct 79 ms 74936 KB Output is correct
10 Correct 59 ms 74936 KB Output is correct
11 Correct 86 ms 78104 KB Output is correct
12 Correct 79 ms 74936 KB Output is correct
13 Correct 79 ms 77972 KB Output is correct
14 Correct 83 ms 75728 KB Output is correct
15 Correct 133 ms 77048 KB Output is correct
16 Correct 129 ms 77180 KB Output is correct
17 Correct 96 ms 77972 KB Output is correct
18 Correct 99 ms 77972 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 77180 KB Output is correct
2 Correct 143 ms 77180 KB Output is correct
3 Correct 379 ms 79188 KB Output is correct
4 Correct 133 ms 77180 KB Output is correct
5 Execution timed out 4000 ms 77180 KB Execution timed out
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 364804 KB Output is correct
2 Correct 936 ms 364804 KB Output is correct
3 Correct 1583 ms 366908 KB Output is correct
4 Correct 966 ms 364804 KB Output is correct
5 Execution timed out 4000 ms 364804 KB Execution timed out
6 Halted 0 ms 0 KB -