oj.uz

Submission #148134

# Submission time Handle Problem Language Result Execution time Memory
148134 2019-08-31T14:10:23 Z WhipppedCream Teams (IOI15_teams) C++17
100 / 100
 3414 ms 343340 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "teams.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 5e5+5;
int n;
int a[maxn], b[maxn];
vii vec;
struct node
{
	int v;
	node *left, *right;
	node(){}
	node(int _v, node *a, node *b)
	{
		v = _v;
		left = a; right = b;
	}
	node* insert(int v, int L = 1, int R = n)
	{
		if(L<= v && v<= R)
		{
			if(L == R) return new node(this->v+1, NULL, NULL);
			int M = (L+R)/2;
			return new node(this->v+1, left->insert(v, L, M), right->insert(v, M+1, R));
		}
		return this;
	}
	int ask(int i, int j, int L = 1, int R = n)
	{
		//printf("asked %d %d\n", i,j );
		if(i> R || j< L) return 0;
		if(i<= L && R<= j) return v;
		int M = (L+R)/2;
		int x = left->ask(i, j, L, M), y = right->ask(i, j, M+1, R);
		return x+y;
	}
};
node *zero;
node* root[maxn];
void init(int N, int A[], int B[])
{
	srand(time(NULL));
	n = N;
	for(int i = 0; i< N; i++) a[i] = A[i], b[i] = B[i];
	for(int i = 0; i< N; i++) vec.pb(ii(a[i], b[i]));
	sort(vec.begin(), vec.end());
	zero = new node(0, NULL, NULL);
	zero->left = zero->right = zero;
	root[0] = zero;
	int ptr = 0;
	for(int i = 1; i<= n; i++)
	{
		root[i] = root[i-1];
		while(ptr< n && vec[ptr].X == i) root[i] = root[i]->insert(vec[ptr++].Y);
	}
}
int era[1100];
int can(int M, int K[])
{
	memset(era, 0, sizeof era);
	int sum = 0;
	for(int i = 0; i< M; i++) sum += K[i];
	if(sum> n) return 0;
	sort(K, K+M);
	vi dis; for(int i = 0; i< M; i++) dis.pb(K[i]);
	sort(dis.begin(), dis.end()); dis.resize(unique(dis.begin(), dis.end())-dis.begin());
	int q = dis.size();
	int tmp;
	for(int i = 0; i< M; i++)
	{
		int x = K[i];
		int ptr = 0;
		while(dis[ptr]< x) ptr++;
		//printf("%d: %d\n", x, ptr);
		if(i == 0 || K[i] != K[i-1]) tmp = ptr;
		while(x && tmp< q)
		{
			//printf("tmp is %d %d\n", tmp, tmp+1< q);
			int here = root[K[i]]->ask(dis[tmp], (tmp+1< q)?dis[tmp+1]-1:n)-era[tmp];
			//printf("from %d to %d is %d\n", dis[tmp], (tmp+1< q)?dis[tmp+1]-1:n, here-era[tmp]);
			if(here<= x)
			{
				x -= here;
				era[tmp] += here;
			}
			else
			{
				era[tmp] += x;
				x = 0;
				break;
			}
			tmp++;
		}
		if(x) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In constructor 'node::node(int, node*, node*)':
teams.cpp:25:2: warning: declaration of 'b' shadows a global declaration [-Wshadow]
  {
  ^
teams.cpp:17:14: note: shadowed declaration is here
 int a[maxn], b[maxn];
              ^
teams.cpp:25:2: warning: declaration of 'a' shadows a global declaration [-Wshadow]
  {
  ^
teams.cpp:17:5: note: shadowed declaration is here
 int a[maxn], b[maxn];
     ^
teams.cpp: In member function 'node* node::insert(int, int, int)':
teams.cpp:30:2: warning: declaration of 'v' shadows a member of 'node' [-Wshadow]
  {
  ^
teams.cpp:21:6: note: shadowed declaration is here
  int v;
      ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(NULL));
        ~~~~^~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:78:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int q = dis.size();
          ~~~~~~~~^~

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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 60136 KB Output is correct
2 Correct 152 ms 60044 KB Output is correct
3 Correct 149 ms 59996 KB Output is correct
4 Correct 160 ms 61604 KB Output is correct
5 Correct 114 ms 59676 KB Output is correct
6 Correct 114 ms 59628 KB Output is correct
7 Correct 114 ms 59628 KB Output is correct
8 Correct 114 ms 59628 KB Output is correct
9 Correct 109 ms 58096 KB Output is correct
10 Correct 106 ms 57452 KB Output is correct
11 Correct 111 ms 60632 KB Output is correct
12 Correct 108 ms 57452 KB Output is correct
13 Correct 121 ms 60628 KB Output is correct
14 Correct 131 ms 58352 KB Output is correct
15 Correct 145 ms 60012 KB Output is correct
16 Correct 146 ms 59936 KB Output is correct
17 Correct 124 ms 60868 KB Output is correct
18 Correct 118 ms 60780 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 60780 KB Output is correct
2 Correct 209 ms 60780 KB Output is correct
3 Correct 344 ms 64252 KB Output is correct
4 Correct 167 ms 61668 KB Output is correct
5 Correct 159 ms 60396 KB Output is correct
6 Correct 155 ms 60524 KB Output is correct
7 Correct 135 ms 60396 KB Output is correct
8 Correct 149 ms 60524 KB Output is correct
9 Correct 109 ms 58128 KB Output is correct
10 Correct 121 ms 58064 KB Output is correct
11 Correct 160 ms 61164 KB Output is correct
12 Correct 1058 ms 58308 KB Output is correct
13 Correct 366 ms 61676 KB Output is correct
14 Correct 300 ms 62444 KB Output is correct
15 Correct 180 ms 60780 KB Output is correct
16 Correct 178 ms 60904 KB Output is correct
17 Correct 143 ms 61680 KB Output is correct
18 Correct 145 ms 61636 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 336668 KB Output is correct
2 Correct 1074 ms 336684 KB Output is correct
3 Correct 1342 ms 343340 KB Output is correct
4 Correct 1010 ms 338088 KB Output is correct
5 Correct 756 ms 333784 KB Output is correct
6 Correct 737 ms 333840 KB Output is correct
7 Correct 672 ms 333920 KB Output is correct
8 Correct 727 ms 333748 KB Output is correct
9 Correct 593 ms 320480 KB Output is correct
10 Correct 638 ms 333180 KB Output is correct
11 Correct 2216 ms 333688 KB Output is correct
12 Correct 3414 ms 334468 KB Output is correct
13 Correct 1616 ms 336356 KB Output is correct
14 Correct 1353 ms 338332 KB Output is correct
15 Correct 922 ms 336688 KB Output is correct
16 Correct 901 ms 336780 KB Output is correct
17 Correct 689 ms 336588 KB Output is correct
18 Correct 689 ms 336588 KB Output is correct