Submission #432286

#	Time	Username	Problem	Language	Result	Execution time	Memory
432286		jeqcho	Teams (IOI15_teams)	C++17	0 / 100	4066 ms	24676 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=b-1;i>=a;--i)
#define R0F(i,b) ROF(i,0,b)
#define trav(a,x) for(auto&a:x)
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define pb push_back
#define sz(x) int(x.size())

int const N=5e5+3;
int A[N],B[N];
int n;
pii stu[N];
int const Q=2e5+3;
int used[N];

template <class T>
struct segmentTree
{
	vector<T>seg;
	vector<T>lazy;
	int arr_sz;
	T initl=-1;
	T comb(T a,T b){return a+b;}
	void pull(int x){seg[x]=comb(seg[2*x+1],seg[2*x+2]);}
	void push(int x,int lx,int rx)
	{
		if(lazy[x]==initl)return;
		seg[x]=(rx-lx)*lazy[x];
		if(rx-lx!=1)
		{
			lazy[2*x+1]=lazy[x];
			lazy[2*x+2]=lazy[x];
		}
		lazy[x]=initl;
	}
	void init(int n1)
	{
		int p=ceil(log2((ld)n1));
		arr_sz=1<<p;
		int tree_sz=arr_sz<<1;
		seg.resize(tree_sz);
		lazy.resize(tree_sz);
		fill(all(lazy),initl);
	}
	T query(int x,int lx,int rx,int lq,int rq)
	{
		push(x,lx,rx);
		if(lq>=rx||rq<=lx)return 0;
		if(lq<=lx&&rq>=rx)return seg[x];
		int md=(lx+rx)/2;
		T lef=query(2*x+1,lx,md,lq,rq);
		T rig=query(2*x+2,md,rx,lq,rq);
		return comb(lef,rig);
	}
	T query(int lq,int rq){return query(0,0,arr_sz,lq,rq);}
	void update(int x,int lx,int rx,int lq,int rq,T v)
	{
		push(x,lx,rx);
		if(lq>=rx||rq<=lx)return;
		if(lq<=lx&&rq>=rx)
		{
			lazy[x]=v;
			push(x,lx,rx);
			return;
		}
		int md=(lx+rx)/2;
		update(2*x+1,lx,md,lq,rq,v);
		update(2*x+2,md,rx,lq,rq,v);
		pull(x);
	}
	void update(int lq,int rq,T v){update(0,0,arr_sz,lq,rq,v);}
};
segmentTree<int>seg;

void init(int n1, int A1[], int B1[]) {
	n=n1;
	F0R(i,n)
	{
		A[i]=A1[i];
		B[i]=B1[i];
		stu[i]={A[i],B[i]};
	}
	sort(stu,stu+n);
	seg.init(n);
}

int can(int m, int K[]) {
	seg.update(0,n,1);
	sort(K,K+m);
	R0F(i,m)
	{
		int l=0;
		int r=K[i];
		int rlim=upper_bound(stu,stu+n,pii{K[i],1e9})-stu;
		vi ans;
		while(l<=r)
		{
			int md=(l+r)/2;
			int idex=lower_bound(stu,stu+n,pii{md,K[i]})-stu;
			int edex=upper_bound(stu,stu+n,pii{md,1e9})-stu;
			int lef=idex;
			int rig=edex;
			int tak=edex;
			int cnt=seg.query(edex,rlim);
			while(lef<=rig)
			{
				int mid=(lef+rig+1)/2;
				if(cnt + seg.query(idex,mid) >= K[i])
				{
					rig=mid-1;
					tak=mid;
				}
				else
				{
					lef=mid+1;
				}
			}
			int cand=cnt+seg.query(idex,tak);
			if(cand>=K[i])
			{
				l=md+1;
				ans={edex,rlim,idex,tak};
			}
			else
			{
				r=md-1;
			}
		}
		if(ans.empty())return 0;
		int cnt = seg.query(ans[0],ans[1]) + seg.query(ans[2],ans[3]);
		seg.update(ans[0],ans[1],0);
		seg.update(ans[2],ans[3],0);
		if(cnt!=K[i])return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:48: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  107 |   int rlim=upper_bound(stu,stu+n,pii{K[i],1e9})-stu;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp:112:48: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  112 |    int idex=lower_bound(stu,stu+n,pii{md,K[i]})-stu;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp:113:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  113 |    int edex=upper_bound(stu,stu+n,pii{md,1e9})-stu;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp: In instantiation of 'void segmentTree<T>::init(int) [with T = int]':
teams.cpp:97:12:   required from here
teams.cpp:51:13: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
   51 |   int p=ceil(log2((ld)n1));
      |         ~~~~^~~~~~~~~~~~~~

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