Submission #502144

#	Time	Username	Problem	Language	Result	Execution time	Memory
502144		MilosMilutinovic	Teams (IOI15_teams)	C++14	100 / 100	3285 ms	155880 KiB

teams

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

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

//namespace ST{
//	int root,ls[M],rs[M],st[M],tsz;
//	void Set(int&c,int ss,int se,int qs,int qe,int x){
//		if(!c)c=++tsz;
//		if(ss>qe||se<qs)return;
//		if(qs<=ss&&se<=qe){st[c]=x;return;}
//		int mid=ss+se>>1;
//		Set(ls[c],ss,mid,qs,qe,x);
//		Set(rs[c],mid+1,se,qs,qe,x);
//	}
//	int Get(int c,int ss,int se,int qi){
//		if(ss==se)return st[c];
//		int mid=ss+se>>1;
//		if(qi<=mid)return max(st[c],Get(ls[c],ss,mid,qi));
//		else return max(st[c],Get(rs[c],mid+1,se,qi));
//	}
//}

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);
	}
}

int cnt[N];
int can(int M,int K[]) {
	ll s=0;
	for(int i=0;i<M;i++)s+=K[i];
	if(s>n)return 0;
	vector<int> val;
	for(int i=0;i<M;i++)val.pb(K[i]),cnt[K[i]]++;
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	int sz=val.size(),nroot=++tsz;
	vector<ll> rem(sz);
	for(int i=0;i<sz;i++){
		int v=val[i];
		ll need=(ll)v*cnt[v];
		for(int j=i;j<sz;j++){
			int nxt=(j==sz-1?n:val[j+1]-1);
			ll x=min(need,Get(root[v],nroot,1,n,val[j],nxt)-rem[j]);
			need-=x; rem[j]+=x;
			if(need==0)break;
			//Set(nroot,1,n,val[j],);
		}
		if(need>0){
			for(int x:val)cnt[x]=0;
			return 0;
		}
	}
	for(int x:val)cnt[x]=0;
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void Set(int&, int, int, int, int, int)':
teams.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'int Get(int, int, int, int, int, int)':
teams.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:44:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   44 | void init(int N,int A[],int B[]) {
      |           ~~~~^
teams.cpp:7:11: note: shadowed declaration is here
    7 | const int N=500050;
      |           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:54:13: warning: declaration of 'M' shadows a global declaration [-Wshadow]
   54 | int can(int M,int K[]) {
      |         ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int M=40*N;
      |           ^
teams.cpp:62:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   62 |  int sz=val.size(),nroot=++tsz;
      |         ~~~~~~~~^~

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