Submission #125599

#	Time	Username	Problem	Language	Result	Execution time	Memory
125599		baluteshih	Teams (IOI15_teams)	C++14	0 / 100	1487 ms	524292 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int n;
vector<int> v[500005];
struct node
{
	int sum=0;
	node *l,*r;
	void up()
	{
		sum=l->sum+r->sum;
	}
}*root[1000005],*ti[500005];

void build(int l,int r,node *&p)
{
	p=new node;
	if(l==r)
		return;
	int m=l+r>>1;
	build(l,m,p->l),build(m+1,r,p->r);
}

node *modify(int x,int l,int r,node *p,int v)
{
	p=new node(*p);
	if(l==r)
		return p->sum+=v,p;
	int m=l+r>>1;
	if(x<=m) p->l=modify(x,l,m,p->l,v);
	else p->r=modify(x,m+1,r,p->r,v);
	return p->up(),p;
}

node *modify2(int x,int l,int r,node *p,int v)
{
	p=new node(*p);
	if(l==r)
		return p->sum=v,p;
	int m=l+r>>1;
	if(x<=m) p->l=modify2(x,l,m,p->l,v);
	else p->r=modify2(x,m+1,r,p->r,v);
	return p->up(),p;
}

int cunt(int x,int l,int r,node *p)
{
	if(l==r) return 0;
	int m=l+r>>1;
	if(x<=m) return cunt(x,l,m,p->l);
	return p->l->sum+cunt(x,m+1,r,p->r);
}

void init(int N, int A[], int B[])
{
	n=N;
	for(int i=0;i<N;++i)
		v[A[i]].pb(B[i]);
	int tp=0;
	build(1,N,root[tp]);
	for(int i=1;i<=N;++i)
	{
		for(int j:v[i])
			root[tp+1]=modify(j,1,n,root[tp],1),++tp;
		if(i>1) root[tp+1]=modify2(i-1,1,n,root[tp],0),++tp;
		ti[i]=root[tp];
	}
}

int can(int M, int K[])
{
	ll ned=0,pre=0,cnt;
	vector<ll> query;
	for(int i=0;i<M;++i)
		query.pb(K[i]);
	sort(ALL(query));
	for(int i=0;i<M;++i)
	{
		ned+=query[i];
		if(ti[query[i]]->sum+pre<ned) return 0;
		if(i+1<M)
		{
			cnt=cunt(query[i+1],1,n,ti[query[i]]);
			if(cnt>=ned-pre)
				pre=ned;
			else
				pre=cnt;
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, node*&)':
teams.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
teams.cpp: In function 'node* modify(int, int, int, node*, int)':
teams.cpp:37:45: warning: declaration of 'v' shadows a global declaration [-Wshadow]
 node *modify(int x,int l,int r,node *p,int v)
                                             ^
teams.cpp:17:13: note: shadowed declaration is here
 vector<int> v[500005];
             ^
teams.cpp:42:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
teams.cpp: In function 'node* modify2(int, int, int, node*, int)':
teams.cpp:48:46: warning: declaration of 'v' shadows a global declaration [-Wshadow]
 node *modify2(int x,int l,int r,node *p,int v)
                                              ^
teams.cpp:17:13: note: shadowed declaration is here
 vector<int> v[500005];
             ^
teams.cpp:53:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
teams.cpp: In function 'int cunt(int, int, int, node*)':
teams.cpp:62:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:96:40: warning: conversion to 'int' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
    cnt=cunt(query[i+1],1,n,ti[query[i]]);
                                        ^

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