oj.uz

답안 #986387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986387 2024-05-20T12:32:56 Z Pyqe 팀들 (IOI15_teams) C++17
100 / 100
 1690 ms 250012 KB 
#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,nsg=0,nn,fq[500069],la[30000069],ra[30000069],sma[30000069],pa[30000069][2],sg[500069],inf=1e9;
pair<int,int> a[2][500069],sk[200069];

void bd(int ix,int lh,int rh)
{
	la[ix]=lh;
	ra[ix]=rh;
	sma[ix]=0;
	if(la[ix]!=ra[ix])
	{
		int ii,md=(la[ix]+ra[ix])/2;
		
		for(ii=0;ii<2;ii++)
		{
			nsg++;
			pa[ix][ii]=nsg;
			bd(nsg,!ii?la[ix]:md+1,!ii?md:ra[ix]);
		}
	}
}

void ud(int ix,int x,int w)
{
	if(la[ix]>=x&&ra[ix]<=x)
	{
		sma[ix]+=w;
	}
	else
	{
		int ii,jj,p;
		
		for(ii=0;ii<2;ii++)
		{
			p=pa[ix][ii];
			if(la[p]<=x&&ra[p]>=x)
			{
				nsg++;
				la[nsg]=la[p];
				ra[nsg]=ra[p];
				sma[nsg]=sma[p];
				for(jj=0;jj<2;jj++)
				{
					pa[nsg][jj]=pa[p][jj];
				}
				pa[ix][ii]=nsg;
				ud(nsg,x,w);
			}
		}
		sma[ix]=sma[pa[ix][0]]+sma[pa[ix][1]];
	}
}

int qr(int ix,int lh,int rh,int sr)
{
	if(la[ix]>rh||ra[ix]<lh)
	{
		return 0;
	}
	else if(la[ix]>=lh&&ra[ix]<=rh)
	{
		return sma[ix]-sma[sr];
	}
	else
	{
		return qr(pa[ix][0],lh,rh,pa[sr][0])+qr(pa[ix][1],lh,rh,pa[sr][1]);
	}
}

int bl(int ix,int x,int sr)
{
	if(la[ix]==ra[ix])
	{
		return la[ix];
	}
	else
	{
		int ii,p,p2;
		
		for(ii=0;ii<2;ii++)
		{
			p=pa[ix][ii];
			p2=pa[sr][ii];
			if(x<=sma[p]-sma[p2])
			{
				return bl(p,x,p2);
			}
			x-=sma[p]-sma[p2];
		}
		return -1;
	}
}

void init(int on,int laa[],int raa[])
{
	int i,ii,k,l;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		k=laa[i-1];
		l=raa[i-1];
		a[0][i]={k,l};
	}
	sort(a[0]+1,a[0]+n+1);
	for(i=1;i<=n;i++)
	{
		l=a[0][i].sc;
		fq[l]++;
		a[1][i]={l,fq[l]};
	}
	sort(a[1]+1,a[1]+n+1);
	for(i=n;i;i--)
	{
		l=a[0][i].sc;
		a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
		fq[l]--;
	}
	nsg++;
	sg[0]=nsg;
	bd(nsg,1,n);
	for(i=1;i<=n;i++)
	{
		l=a[0][i].sc;
		nsg++;
		la[nsg]=la[sg[i-1]];
		ra[nsg]=ra[sg[i-1]];
		sma[nsg]=sma[sg[i-1]];
		for(ii=0;ii<2;ii++)
		{
			pa[nsg][ii]=pa[sg[i-1]][ii];
		}
		sg[i]=nsg;
		ud(nsg,l,1);
	}
}

int can(int sz,int qq[])
{
	int i,k,l,w,sm;
	
	sort(qq,qq+sz);
	nn=0;
	for(i=0;i<sz;i++)
	{
		sm=qq[i];
		k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
		l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
		for(;nn;nn--)
		{
			w=qr(sg[k],l+1,sk[nn].sc-1,sg[sk[nn].fr]);
			if(w>sm)
			{
				break;
			}
			l=max(l,sk[nn].sc);
			sm-=w;
		}
		l=bl(sg[k],qr(sg[k],1,l,sg[sk[nn].fr])+sm,sg[sk[nn].fr]);
		if(l==-1)
		{
			return 0;
		}
		nn++;
		sk[nn]={k,l};
	}
	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:124:54: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  124 |   a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:155:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  155 |   k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:156:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  156 |   l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 2 ms 14680 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 2 ms 14788 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 2 ms 14680 KB Output is correct
16 Correct 2 ms 14680 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 2 ms 14684 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 2 ms 14684 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14680 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 2 ms 14684 KB Output is correct
26 Correct 2 ms 14684 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 54960 KB Output is correct
2 Correct 89 ms 54920 KB Output is correct
3 Correct 101 ms 55184 KB Output is correct
4 Correct 91 ms 55136 KB Output is correct
5 Correct 41 ms 54364 KB Output is correct
6 Correct 42 ms 54528 KB Output is correct
7 Correct 41 ms 54540 KB Output is correct
8 Correct 42 ms 54356 KB Output is correct
9 Correct 63 ms 54508 KB Output is correct
10 Correct 47 ms 54608 KB Output is correct
11 Correct 39 ms 54532 KB Output is correct
12 Correct 38 ms 54540 KB Output is correct
13 Correct 51 ms 54580 KB Output is correct
14 Correct 50 ms 54888 KB Output is correct
15 Correct 78 ms 54944 KB Output is correct
16 Correct 82 ms 54956 KB Output is correct
17 Correct 42 ms 54868 KB Output is correct
18 Correct 50 ms 54920 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 55672 KB Output is correct
2 Correct 104 ms 55216 KB Output is correct
3 Correct 328 ms 58192 KB Output is correct
4 Correct 94 ms 55168 KB Output is correct
5 Correct 129 ms 54864 KB Output is correct
6 Correct 122 ms 54868 KB Output is correct
7 Correct 47 ms 54900 KB Output is correct
8 Correct 102 ms 54996 KB Output is correct
9 Correct 64 ms 54536 KB Output is correct
10 Correct 101 ms 54796 KB Output is correct
11 Correct 130 ms 54868 KB Output is correct
12 Correct 173 ms 55124 KB Output is correct
13 Correct 272 ms 54864 KB Output is correct
14 Correct 361 ms 56660 KB Output is correct
15 Correct 108 ms 55276 KB Output is correct
16 Correct 111 ms 55380 KB Output is correct
17 Correct 76 ms 55200 KB Output is correct
18 Correct 77 ms 55120 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 797 ms 235676 KB Output is correct
2 Correct 797 ms 242756 KB Output is correct
3 Correct 1515 ms 250012 KB Output is correct
4 Correct 789 ms 242760 KB Output is correct
5 Correct 526 ms 238284 KB Output is correct
6 Correct 548 ms 238780 KB Output is correct
7 Correct 247 ms 238284 KB Output is correct
8 Correct 504 ms 238520 KB Output is correct
9 Correct 365 ms 238456 KB Output is correct
10 Correct 453 ms 236764 KB Output is correct
11 Correct 627 ms 237376 KB Output is correct
12 Correct 723 ms 238348 KB Output is correct
13 Correct 1255 ms 240364 KB Output is correct
14 Correct 1690 ms 246612 KB Output is correct
15 Correct 649 ms 242724 KB Output is correct
16 Correct 628 ms 242864 KB Output is correct
17 Correct 342 ms 241916 KB Output is correct
18 Correct 336 ms 242044 KB Output is correct