oj.uz

Submission #1057715

# Submission time Handle Problem Language Result Execution time Memory
1057715 2024-08-14T03:59:31 Z MuhammadSaram Teams (IOI15_teams) C++17
0 / 100
 2086 ms 104076 KB 
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;
 
const int M = 5e5 + 1;
 
#define all(v) v.begin(), v.end()
 
int n,pre[M];
vector<int> V,seg[M*2];
 
void make(int v=0,int s=0,int e=n)
{
	for (int i=s;i<e;i++)
		seg[v].push_back(V[i]);
	sort(all(seg[v]));
	if (s+1==e)
		return;
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	make(lc,s,mid);
	make(rc,mid,e);
}
 
int get(int l,int r,int x,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s)
		return 0;
	if (l<=s && e<=r)
	{
		int y=upper_bound(all(seg[v]),x)-begin(seg[v]);
		return y;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return get(l,r,x,lc,s,mid)+get(l,r,x,rc,mid,e);
}
 
void init(int N,int A[],int B[])
{
	n=N;
	vector<pair<int,int>> v1;
	for (int i=0;i<n;i++)
		v1.push_back({B[i],A[i]}),pre[B[i]]++;
	sort(v1.begin(),v1.end());
	for (auto i:v1)
		V.push_back(i.second);
	for (int i=1;i<M;i++)
		pre[i]+=pre[i-1];
	make();
}
 
int can(int m,int k[])
{
	sort(k,k+m);
	reverse(k,k+m);
	int val=n;
	for (int i=0;i<m;i++)
	{
		int s=pre[k[i]-1]-1,e=val;
		while (s+1<e)
		{
			int mid=(s+e)/2;
			if (get(mid,val,k[i])>=k[i])
				s=mid;
			else
				e=mid;
		}
		if (s==pre[k[i]-1]-1)
			return 0;
		val=s;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int get(int, int, int, int, int, int)':
teams.cpp:31:35: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   31 |   int y=upper_bound(all(seg[v]),x)-begin(seg[v]);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25692 KB Output is correct
2 Correct 3 ms 25692 KB Output is correct
3 Correct 5 ms 25692 KB Output is correct
4 Correct 3 ms 25692 KB Output is correct
5 Correct 3 ms 25720 KB Output is correct
6 Correct 4 ms 25692 KB Output is correct
7 Correct 4 ms 25692 KB Output is correct
8 Correct 4 ms 25692 KB Output is correct
9 Correct 4 ms 25692 KB Output is correct
10 Correct 4 ms 25692 KB Output is correct
11 Correct 3 ms 25692 KB Output is correct
12 Correct 6 ms 25692 KB Output is correct
13 Incorrect 4 ms 25900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 40948 KB Output is correct
2 Correct 74 ms 40900 KB Output is correct
3 Correct 74 ms 40904 KB Output is correct
4 Correct 75 ms 40904 KB Output is correct
5 Correct 36 ms 40760 KB Output is correct
6 Correct 37 ms 40912 KB Output is correct
7 Correct 44 ms 40908 KB Output is correct
8 Correct 37 ms 41492 KB Output is correct
9 Correct 109 ms 41708 KB Output is correct
10 Correct 72 ms 41424 KB Output is correct
11 Correct 38 ms 41412 KB Output is correct
12 Correct 34 ms 41424 KB Output is correct
13 Correct 41 ms 41668 KB Output is correct
14 Correct 41 ms 41924 KB Output is correct
15 Incorrect 70 ms 41928 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 40760 KB Output is correct
2 Correct 79 ms 40904 KB Output is correct
3 Correct 549 ms 43444 KB Output is correct
4 Correct 75 ms 40796 KB Output is correct
5 Correct 160 ms 40912 KB Output is correct
6 Correct 107 ms 40900 KB Output is correct
7 Correct 169 ms 40904 KB Output is correct
8 Correct 109 ms 41928 KB Output is correct
9 Correct 110 ms 41680 KB Output is correct
10 Correct 267 ms 41492 KB Output is correct
11 Correct 293 ms 41668 KB Output is correct
12 Incorrect 331 ms 41712 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 99512 KB Output is correct
2 Correct 435 ms 99516 KB Output is correct
3 Correct 2086 ms 102256 KB Output is correct
4 Correct 416 ms 99512 KB Output is correct
5 Correct 485 ms 99508 KB Output is correct
6 Correct 364 ms 99508 KB Output is correct
7 Correct 496 ms 99512 KB Output is correct
8 Correct 376 ms 103612 KB Output is correct
9 Correct 721 ms 104076 KB Output is correct
10 Correct 972 ms 102496 KB Output is correct
11 Correct 1132 ms 102660 KB Output is correct
12 Incorrect 1251 ms 103356 KB Output isn't correct
13 Halted 0 ms 0 KB -