Submission #501950

#	Time	Username	Problem	Language	Result	Execution time	Memory
501950		MilosMilutinovic	팀들 (IOI15_teams)	C++14	0 / 100	1916 ms	190348 KiB

teams

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

const int N=500050;
const int M=40*N;

int n,ls[M],rs[M],st[M],root[N],tsz;
void Set(int&c,int p,int ss,int se,int qi,int x){
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];st[c]=st[p]+x;
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ls[p],ss,mid,qi,x);
	else Set(rs[c],rs[p],mid+1,se,qi,x);
}
int Get(int c,int p,int ss,int se,int qs,int qe){
	if(qs>qe||ss>qe||se<qs)return 0;
	if(qs<=ss&&se<=qe)return st[c]-st[p];
	int mid=ss+se>>1;
	return Get(ls[c],ls[p],ss,mid,qs,qe)+Get(rs[c],rs[p],mid+1,se,qs,qe);
}

vector<int> Qs[N];
void init(int N,int A[],int B[]) {
	n=N;
	for(int i=0;i<n;i++)Qs[A[i]].pb(B[i]);
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		for(int x:Qs[i])Set(root[i],root[i],1,n,x,1);
	}
	//printf(":%d\n\n",Get(root[2],root[0],1,n,1,3));
}

int can(int M,int K[]) {
	sort(K,K+M);
	int nroot=++tsz,ptr=0;
	for(int i=0;i<M;i++){
		ptr=max(ptr,K[i]);
		int tot=Get(root[K[i]],nroot,1,n,ptr,n);
		if(tot<K[i])return 0;
		int bot=ptr,top=n,pos=-1;
		while(bot<=top){
			int mid=bot+top>>1;
			if(Get(root[K[i]],nroot,1,n,ptr,mid)>=K[i])pos=mid,top=mid-1;
			else bot=mid+1;
		}
		//if(K[0]==1&&K[1]==1)printf("::%d\n",pos);
		assert(pos!=-1);
		int prv_s=Get(root[K[i]],nroot,1,n,ptr,pos-1);
		//if(K[0]==1&&K[1]==1)printf(":::%d\n",prv_s);
		Set(nroot,nroot,1,n,pos,(K[i]-prv_s));
		ptr=max(ptr,pos);
	}
	return 1;
}

/*
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1
*/

Compilation message (stderr)

teams.cpp: In function 'void Set(int&, int, int, int, int, int)':
teams.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'int Get(int, int, int, int, int, int)':
teams.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:25:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   25 | void init(int N,int A[],int B[]) {
      |           ~~~~^
teams.cpp:6:11: note: shadowed declaration is here
    6 | const int N=500050;
      |           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:35:13: warning: declaration of 'M' shadows a global declaration [-Wshadow]
   35 | int can(int M,int K[]) {
      |         ~~~~^
teams.cpp:7:11: note: shadowed declaration is here
    7 | const int M=40*N;
      |           ^
teams.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |    int mid=bot+top>>1;
      |            ~~~^~~~

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