Submission #569600

#	Time	Username	Problem	Language	Result	Execution time	Memory
569600		CSQ31	Teams (IOI15_teams)	C++17	77 / 100	4061 ms	406272 KiB

teams

#pragma GCC optimize("Ofast") 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
vector<pii>r;
struct node{
	node *lf = NULL,*rg = NULL;
	int cnt = 0;
	node(){}
	node(node *v){
		lf = v->lf;
		rg = v->rg;
		cnt = v->cnt;
	}
	int query(int s,int e,int l=1,int r=n){
		if(l==s && r==e)return cnt;
		int tm = (l+r)/2;
		if(s > tm)return rg?rg->query(s,e,tm+1,r):0;
		else if(e<=tm)return lf?lf->query(s,e,l,tm):0;
		int res = 0;
		if(lf)res+=lf->query(s,tm,l,tm);
		if(rg)res+=rg->query(tm+1,e,tm+1,r);
		return res;
	}
};
node*update(node *v,int l,int r,int pos,int x){
	if(l==r){
		node *res = new node(v);
		res->cnt+=x;
		return res;
	}
	int tm = (l+r)/2;
	node* res = new node(v);
	if(pos<=tm){
		if(!v->lf)v->lf = new node();
		res->lf = update(v->lf,l,tm,pos,x);
	}
	else {
		if(!v->rg)v->rg = new node();
		res->rg = update(v->rg,tm+1,r,pos,x);
	}
	res->cnt = 0;
	if(res->lf)res->cnt+=res->lf->cnt;
	if(res->rg)res->cnt+=res->rg->cnt;
	return res;
}
vector<node*>root;
void init(int N, int A[], int B[]) {
	n = N;
	vector<map<int,int>>cnt(n+1);
	for(int i=0;i<n;i++)cnt[A[i]][B[i]]++;
	root.push_back(new node());
	for(int i=1;i<=n;i++){
		root.push_back(new node(root.back()));
		for(pii x:cnt[i])root.back() = update(root.back(),1,n,x.fi,x.se);
		//cout<<root.back()->query(1,n)<<'\n';
	}
}
 
int can(int m, int K[]) {
	int sum = 0;
	map<int,int>cnt;
	for(int i=0;i<m;i++){
		sum+=K[i];
		cnt[K[i]]++;
		if(sum>n)return 0;
	}
	vector<pii>a;
	for(auto x:cnt)a.push_back(x);
	a.push_back({n+1,0});
	int s = a.size();
	//for(pii x:a)cout<<x.fi<<" ";
	//cout<<'\n';
	vector<int>need(s,0);
	vector<int>have(s,0);
	for(int i=0;i<s;i++)need[i] = a[i].fi * a[i].se;
	for(int i=0;i<s;i++){
		int l = 0,r = a[i].fi;
		if(i)l = a[i-1].fi;
		for(int j=i;j+1<s;j++){
			int L = a[j].fi;
			int R = a[j+1].fi-1;
			have[j]+=root[r]->query(L,R);
			have[j]-=root[l]->query(L,R);
		}
		for(int j=i;j<s;j++){
			if(!need[i])break;
			if(have[j]){
				int tmp = min(have[j],need[i]);
				need[i]-=tmp;
				have[j]-=tmp;
			}
		}
	}
	//for(int x:need)cout<<x<<" ";
	for(int x:need){
		if(x)return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int node::query(int, int, int, int)':
teams.cpp:19:36: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   19 |  int query(int s,int e,int l=1,int r=n){
      |                                ~~~~^~~
teams.cpp:9:12: note: shadowed declaration is here
    9 | vector<pii>r;
      |            ^
teams.cpp: In function 'node* update(node*, int, int, int, int)':
teams.cpp:30:31: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   30 | node*update(node *v,int l,int r,int pos,int x){
      |                           ~~~~^
teams.cpp:9:12: note: shadowed declaration is here
    9 | vector<pii>r;
      |            ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:75:16: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  int s = a.size();
      |          ~~~~~~^~
teams.cpp:82:13: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   82 |   int l = 0,r = a[i].fi;
      |             ^
teams.cpp:9:12: note: shadowed declaration is here
    9 | vector<pii>r;
      |            ^

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