oj.uz

Submission #45877

# Submission time Handle Problem Language Result Execution time Memory
45877 2018-04-16T09:56:42 Z RayaBurong25_1 Teams (IOI15_teams) C++17
100 / 100
 3986 ms 420536 KB 
#include "teams.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
#define INF 1000000007
typedef struct point point;
struct point
{
	int a, b;
};
typedef struct node node;
struct node
{
	int sum;
	node* l;
	node* r;
};
int n;
node* root[500005];
int whichroot[500005];
int sortAB(point a, point b)
{
	return (a.a < b.a || (a.a == b.a && a.b < b.b));
}
int max(int a, int b)
{
	return (a > b)?a:b;
}
int min(int a, int b)
{
	return (a < b)?a:b;
}
node* makeTree(int s, int e)
{
	// printf("makeTree %d %d\n", s, e);
	if (s == e)
	{
		node* p = new node();
		p->sum = 0;
		p->l = NULL;
		p->r = NULL;
		return p;
	}
	int m = (s + e)/2;
	node* p = new node();
	p->sum = 0;
	p->l = makeTree(s, m);
	p->r = makeTree(m + 1, e);
	return p;
}
node* update(node* p, int s, int e, int v)
{
	// printf("update p%p s%d e%d v%d\n", p, s, e, v);
	if (s == e)
	{
		node* q = new node();
		q->sum = p->sum + 1;
		q->l = NULL;
		q->r = NULL;
		return q;
	}
	int m = (s + e)/2;
	node* q = new node();
	if (v <= m)
	{
		q->l = update(p->l, s, m, v);
		q->r = p->r;
	}
	else
	{
		q->l = p->l;
		q->r = update(p->r, m + 1, e, v);
	}
	q->sum = q->l->sum + q->r->sum;
	return q;
}
void init(int N, int A[], int B[])
{
	n = N;
	std::vector<point> P;
	int i;
	for (i = 0; i < N; i++)
		P.push_back({A[i], B[i]});
	std::sort(P.begin(), P.end(), sortAB);
	root[0] = makeTree(1, N);
	for (i = 1; i <= N; i++)
	{
		root[i] = update(root[i - 1], 1, N, P[i - 1].b);
		whichroot[P[i - 1].a] = i;
	}
	for (i = 1; i <= N; i++)
		whichroot[i] = max(whichroot[i], whichroot[i - 1]);
	// printf("init ok\n");
}
std::vector<std::pair<std::pair<int, int>, int> > Stairs;
int query(int Xmn, int Xmx, int Y)
{
	// printf("query Xmn%d Xmx%d Y%d\n", Xmn, Xmx, Y);
	if (Y < 1)
		return 0;
	node* p = root[whichroot[Xmx]];
	node* q = root[whichroot[Xmn]];
	int s = 1, e = n;
	int m, r = 0;
	while (s != e)
	{
		m = (s + e)/2;
		if (Y <= m)
		{
			p = p->l;
			q = q->l;
			e = m;
		}
		else
		{
			r += p->l->sum - q->l->sum;
			p = p->r;
			q = q->r;
			s = m + 1;
		}
	}
	r += p->sum - q->sum;
	return r;
}
int compStair(std::pair<std::pair<int, int>, int> e, int v)
{
	return e.first.second > v;
}
int sumBoys(int Xmx, int Y)
{
	// printf("sumBoys Xmx%d Y%d\n", Xmx, Y);
	int i;
	i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
	i--;
	int Xmn = Stairs[i].first.first;
	// printf("Xmn %d\n", Xmn);
	int Q = query(Xmn, Xmx, Y) - (Stairs.back().second - Stairs[i].second);
	// printf("Q %d\n", Q);
	return Q;
}
void updStairs(int X, int Y, int K)
{
	int sum = 0;
	while (Stairs.back().first.second <= Y)
	{
		sum += Stairs.back().second;
		Stairs.pop_back();
		sum -= Stairs.back().second;
	}
	Stairs.push_back({{X, Y}, Stairs.back().second + sum + K});
	// int i;
	// for (i = 0; i < Stairs.size(); i++)
		// printf("Stairs %d %d %d\n", Stairs[i].first.first, Stairs[i].first.second, Stairs[i].second);
}
int can(int M, int K[])
{
	std::sort(&K[0], &K[M]);
	Stairs.clear();
	Stairs.push_back({{0, INF}, 0});
	int i;
	int mn, md, mx;
	int sb, kisb;
	for (i = 0; i < M; i++)
	{
		mn = K[i] - 1;
		mx = n;
		sb = sumBoys(K[i], mn);
		if (sumBoys(K[i], mx) < K[i] + sb)
			return 0;
		kisb = K[i] + sb;
		while (1)
		{
			// printf("mn %d mx %d\n", mn, mx);
			if (mx - mn <= 1)
			{
				md = mx;
				break;
			}
			md = (mn + mx)/2;
			if (sumBoys(K[i], md) >= kisb)
				mx = md;
			else
				mn = md;
		}
		updStairs(K[i], md, kisb);
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int sumBoys(int, int)':
teams.cpp:133:67: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
  i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 2 ms 716 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 716 KB Output is correct
23 Correct 2 ms 716 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 65128 KB Output is correct
2 Correct 239 ms 65128 KB Output is correct
3 Correct 203 ms 65164 KB Output is correct
4 Correct 207 ms 65164 KB Output is correct
5 Correct 125 ms 65164 KB Output is correct
6 Correct 125 ms 65164 KB Output is correct
7 Correct 124 ms 65164 KB Output is correct
8 Correct 127 ms 65164 KB Output is correct
9 Correct 159 ms 65164 KB Output is correct
10 Correct 131 ms 65164 KB Output is correct
11 Correct 134 ms 65956 KB Output is correct
12 Correct 136 ms 65956 KB Output is correct
13 Correct 143 ms 65956 KB Output is correct
14 Correct 131 ms 65956 KB Output is correct
15 Correct 173 ms 65956 KB Output is correct
16 Correct 193 ms 65956 KB Output is correct
17 Correct 139 ms 66100 KB Output is correct
18 Correct 139 ms 66100 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 66100 KB Output is correct
2 Correct 195 ms 66100 KB Output is correct
3 Correct 750 ms 67676 KB Output is correct
4 Correct 177 ms 67676 KB Output is correct
5 Correct 286 ms 67676 KB Output is correct
6 Correct 267 ms 67676 KB Output is correct
7 Correct 141 ms 67676 KB Output is correct
8 Correct 231 ms 67676 KB Output is correct
9 Correct 152 ms 67676 KB Output is correct
10 Correct 209 ms 67676 KB Output is correct
11 Correct 227 ms 67676 KB Output is correct
12 Correct 293 ms 67676 KB Output is correct
13 Correct 535 ms 67676 KB Output is correct
14 Correct 1004 ms 67676 KB Output is correct
15 Correct 293 ms 67676 KB Output is correct
16 Correct 303 ms 67676 KB Output is correct
17 Correct 258 ms 67676 KB Output is correct
18 Correct 261 ms 67676 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 358072 KB Output is correct
2 Correct 1177 ms 358188 KB Output is correct
3 Correct 3550 ms 360824 KB Output is correct
4 Correct 1470 ms 360824 KB Output is correct
5 Correct 1451 ms 360824 KB Output is correct
6 Correct 1139 ms 360824 KB Output is correct
7 Correct 754 ms 360824 KB Output is correct
8 Correct 995 ms 362264 KB Output is correct
9 Correct 892 ms 362264 KB Output is correct
10 Correct 922 ms 370988 KB Output is correct
11 Correct 1123 ms 374532 KB Output is correct
12 Correct 1330 ms 378856 KB Output is correct
13 Correct 2853 ms 384696 KB Output is correct
14 Correct 3986 ms 390940 KB Output is correct
15 Correct 1446 ms 399700 KB Output is correct
16 Correct 1443 ms 406924 KB Output is correct
17 Correct 1071 ms 413952 KB Output is correct
18 Correct 1048 ms 420536 KB Output is correct