Submission #133242

#	Time	Username	Problem	Language	Result	Execution time	Memory
133242		ckodser	Teams (IOI15_teams)	C++14	34 / 100	4099 ms	136816 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"

#define ll int
#define F first
#define S second
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair

using namespace :: std;

const ll maxn=5e5+500;
const ll inf=1e9+900;
const ll sq=1050;


ll Gn;
ll mna[maxn*4];
ll mxa[maxn*4];
vector<ll> seg[maxn*4];
pii rr[maxn];
void bild(ll l,ll r,ll node){
    mna[node]=rr[l].F;
    mxa[node]=rr[r-1].F;
    for(ll i=l;i<r;i++){
	seg[node].pb(rr[i].S);
    }	
    sort(seg[node].begin(),seg[node].end());
    if(l+1==r)return;
    ll mid=(l+r)/2;
    bild(l,mid,2*node);
    bild(mid,r,2*node+1);
}
ll findAz(ll l,ll r,ll node=1){
    if(l<mna[node])return 0;
    if(mxa[node]<=l){
	return seg[node].end()-lower_bound(seg[node].begin(),seg[node].end(),r);
    }
    return findAz(l,r,2*node)+findAz(l,r,2*node+1);
}
ll A[maxn];
ll B[maxn];
void init(int n, int a[], int b[]) {
    Gn=n;
    for(ll i=0;i<n;i++){
	A[i]=a[i];
	B[i]=b[i];
	rr[i]=mp(a[i],b[i]);
    }
    sort(rr,rr+n);
    bild(0,n,1);
}


ll ger[sq][sq];
ll tmp[sq];
bool canslow(ll m,ll k[]){
    memset(tmp,0,sizeof tmp);
    for(ll i=0;i<m;i++){
	ll v=k[i];
	for(ll j=i;j<m;j++){
	    tmp[j]+=ger[i][j];
	}
	for(ll j=i;j<m && v;j++){
	    if(v<=tmp[j]){
		tmp[j]-=v;
		v=0;
	    }else{
		v-=tmp[j];
		tmp[j]=0;
	    }
	}
	if(v)return 0;
    }
    return 1;
}


void bildGer(ll m,ll k[]){
    for(ll i=0;i<m;i++)for(ll j=0;j<m;j++)ger[i][j]=0;

    for(ll i=0;i<Gn;i++){
	ll l=lower_bound(k,k+m,A[i])-k;
	ll r=upper_bound(k,k+m,B[i])-k-1;
	ger[l][r]++;
    }
    return;
    for(ll t=m;t>=1;t--){
	for(ll l=0;l+t-1<m;l++){
	    ll r=l+t-1;
	    ger[l][r]=findAz(k[l],k[r]);
	    if(r+1<m)
		ger[l][r]-=ger[l][r+1];
	    if(l)
		ger[l][r]-=ger[l-1][r];
	    if(l && r+1<m)
		ger[l][r]+=ger[l-1][r+1];
	}
    }
}
ll K[sq];
ll cnt[sq];
int can(int m, int k[]) {
    sort(k,k+m);
    memset(cnt,0,sizeof cnt);
    ll sum=0;
    for(ll i=0;i<m;i++){
	sum+=k[i];
	K[i]=k[i];
    }
    if(sum>Gn)return 0;
    
    ll sz=unique(K,K+m)-K;
    for(ll i=0;i<m;i++){
	ll t=(lower_bound(K,K+sz,k[i])-K);
	cnt[t]++;
    }
    bildGer(sz,K);
    for(ll i=0;i<sz;i++){
	K[i]*=cnt[i];
    }
    return canslow(sz,K);
}

Compilation message (stderr)

teams.cpp: In function 'int findAz(int, int, int)':
teams.cpp:38:24: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  return seg[node].end()-lower_bound(seg[node].begin(),seg[node].end(),r);
         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void bildGer(int, int*)':
teams.cpp:84:30: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  ll l=lower_bound(k,k+m,A[i])-k;
       ~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:85:32: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  ll r=upper_bound(k,k+m,B[i])-k-1;
       ~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:24: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
     ll sz=unique(K,K+m)-K;
           ~~~~~~~~~~~~~^~
teams.cpp:116:32: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  ll t=(lower_bound(K,K+sz,k[i])-K);
       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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