Submission #155930

#	Time	Username	Problem	Language	Result	Execution time	Memory
155930		junodeveloper	Teams (IOI15_teams)	C++14	0 / 100	1012 ms	139500 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
const int maxn=500000;
const int tmax=20*maxn+4*maxn;
int n,m;
int root[maxn+10];
int tree[tmax],tl[tmax],tr[tmax],tcnt;
vector<int> vx,vy;
int build(int s,int e) {
	int u=++tcnt;
	tree[u]=0;
	if(s==e) return u;
	int mid=(s+e)/2;
	tl[u]=build(s,mid);
	tr[u]=build(mid+1,e);
	return u;
}
int update(int u,int s,int e,int p,int x) {
	if(p<s||e<p) return u;
	int nu=++tcnt;
	tree[nu]=tree[u]+x;
	if(s==e) return nu;
	int mid=(s+e)/2;
	tl[nu]=update(tl[u],s,mid,p,x);
	tr[nu]=update(tr[u],mid+1,e,p,x);
	return nu;
}
int query(int u,int s,int e,int l,int r) {
	if(l>r) return 0;
	if(e<l||r<s) return 0;
	if(l<=s&&e<=r) return tree[u];
	int mid=(s+e)/2;
	return query(tl[u],s,mid,l,r)+query(tr[u],mid+1,e,l,r);
}
void init(int N, int A[], int B[]) {
	n=N;
	vector<int> a;
	int i,j;
	for(i=0;i<n;i++)a.push_back(i);
	sort(a.begin(),a.end(),[&](int x,int y) {
		return B[x]<B[y];
	});
	for(i=0;i<n;i++) {
		vx.push_back(A[a[i]]);
		vy.push_back(B[a[i]]);
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	root[n]=build(0,sz(vx)-1);
	for(i=n-1;i>=0;i--) {
		j=lower_bound(vx.begin(),vx.end(),A[a[i]])-vx.begin();
		root[i]=update(root[i+1],0,sz(vx)-1,j,1);
	}
}

int can(int M, int K[]) {
	m=M;
	int i,j,k;
	sort(K,K+m);
	int mx=0,q1,q2,cur=0;
	for(i=0;i<m;i++) {
		j=lower_bound(vy.begin(),vy.end(),K[i])-vy.begin();
		k=lower_bound(vx.begin(),vx.end(),K[i]+1)-vx.begin()-1;
		q1=query(root[j],0,sz(vx)-1,0,k);
		if(i) { 
			k=lower_bound(vx.begin(),vx.end(),K[i-1]+1)-vx.begin()-1;
			q2=query(root[j],0,sz(vx)-1,0,k);
		} else q2=0;
		cur=1-q1+max(0,cur+q2);
		mx=max(mx,cur);
	}
	return mx<=0;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:45: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   j=lower_bound(vx.begin(),vx.end(),A[a[i]])-vx.begin();
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:64:42: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   j=lower_bound(vy.begin(),vy.end(),K[i])-vy.begin();
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:65:55: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   k=lower_bound(vx.begin(),vx.end(),K[i]+1)-vx.begin()-1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:68:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
    k=lower_bound(vx.begin(),vx.end(),K[i-1]+1)-vx.begin()-1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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