Submission #559122

#	Time	Username	Problem	Language	Result	Execution time	Memory
559122		Koosha_mv	Teams (IOI15_teams)	C++14	0 / 100	279 ms	53620 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "teams.h"

const int N=2e5+99;

int n,t,A[N],B[N];
vector<int> seg[N<<2];

vector<int> merge(vector<int> &vec1,vector<int> &vec2){
	int p1=0,p2=0;
	vector<int> ans;
	while(p1<vec1.size() || p2<vec2.size()){
		if(p2==vec2.size() || (p1<vec1.size() && vec1[p1]<vec2[p2])){
			ans.pb(vec1[p1++]);
		}
		else{
			ans.pb(vec2[p2++]);
		}
	}	
	return ans;
}
void build(int id=1,int l=1,int r=n+1){
	if(l+1==r){
		seg[id].pb(A[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid,r);
	seg[id]=merge(seg[id<<1],seg[id<<1|1]);
}
void init(int _n, int _A[], int _B[]) {
	n=_n;
	vector<int> vec(n);
	iota(all(vec),0);
	sort(all(vec),[&](int i,int j){ return _B[i]<_B[j]; });
	f(i,0,n) A[i+1]=_A[vec[i]],B[i+1]=_B[vec[i]];
	build();
}
int calc(int id,int x){
	return upper_bound(all(seg[id]),x)-seg[id].begin();
}
int get(int L,int R,int val,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return 0;
	if(L<=l && r<=R){
		return calc(id,val);
	}
	int mid=(l+r)>>1;
	return get(L,R,val,id<<1,l,mid)+get(L,R,val,id<<1|1,mid,r);
}
int solve(int cnt,int val,int id=1,int l=1,int r=n+1){
	if(l+1==r){
		return r;
	}
	int mid=(l+r)>>1;
	if(calc(id<<1,val)>=cnt) return solve(cnt,val,id<<1,l,mid);
	cnt-=calc(id<<1,val);
	return solve(cnt,val,id<<1|1,mid,r);
}
int can(int m, int K[]) {
	int p=1;
	f(i,0,m){
		int x=K[i];
		maxm(p,int(lower_bound(B+1,B+n+1,x)-B));
		if(p==n+1) return 0;
		int cnt=get(1,p,x);
		if(calc(1,x)<cnt+x) return 0;
		p=solve(cnt+x,x);
	}
	return 1;
}
/*
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int a[20],b[20];
	cin>>n;
	f(i,0,n) cin>>a[i]>>b[i];
	init(n,a,b);
	cin>>t;
	while(t--){
		int m;
		cin>>m;
		f(i,0,m) cin>>a[i];
		cout<<can(m,a)<<" - ans"<<endl;
	}
}*/
/*
4
1 2
2 3
2 3
2 4
*/

Compilation message (stderr)

teams.cpp: In function 'std::vector<int> merge(std::vector<int>&, std::vector<int>&)':
teams.cpp:32:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  while(p1<vec1.size() || p2<vec2.size()){
      |        ~~^~~~~~~~~~~~
teams.cpp:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  while(p1<vec1.size() || p2<vec2.size()){
      |                          ~~^~~~~~~~~~~~
teams.cpp:33:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if(p2==vec2.size() || (p1<vec1.size() && vec1[p1]<vec2[p2])){
      |      ~~^~~~~~~~~~~~~
teams.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if(p2==vec2.size() || (p1<vec1.size() && vec1[p1]<vec2[p2])){
      |                          ~~^~~~~~~~~~~~
teams.cpp: In function 'int calc(int, int)':
teams.cpp:61:36: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   61 |  return upper_bound(all(seg[id]),x)-seg[id].begin();
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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