oj.uz

Submission #924291

# Submission time Handle Problem Language Result Execution time Memory
924291 2024-02-08T19:31:22 Z Macker Teams (IOI15_teams) C++14
0 / 100
 459 ms 90704 KB 
#include "teams.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

vector<vector<int>> st;
int len = 1;

int qry(int l, int r, int val, int i = 1, int s = 0, int e = len){
	if(l >= e || s >= r) return 0;
	if(l <= s && e <= r){
		return upper_bound(all(st[i]), val) - st[i].begin();
	}
	return qry(l, r, val, i * 2, s, (s + e) / 2) +
		qry(l, r, val, i * 2 + 1,(s + e) / 2, e);
}

void init(int N, int A[], int B[]) {
	while(len < N + 1) len *= 2;
	st.resize(2 * len);
	for (int i = 0; i < N; i++) {
		st[len + B[i]].push_back(A[i]);
	}
	
	for (int i = len; i < 2 * len; i++) sort(all(st[i]));
	for (int i = len - 1; i > 0; i--) {
		int j = 0, k = 0;
		st[i].reserve(st[i * 2].size() + st[i * 2 + 1].size());
		while(j < st[i * 2].size() && k < st[i * 2 + 1].size()){
			if(st[i * 2][j] < st[i * 2 + 1][k]){
				st[i].push_back(st[i * 2][j++]);
			}
			else{
				st[i].push_back(st[i * 2 + 1][k++]);
			}
		}
		for (; j < st[i * 2].size(); j++) st[i].push_back(st[i * 2][j]);
		for (; k < st[i * 2 + 1].size(); k++) st[i].push_back(st[i * 2 + 1][k]);
	}
	
}

int can(int M, int K[]) {
	sort(K, K + M, greater<int>());
	int rem = 0;
	for (int i = 0; i < M; i++) {
		int my, a, b;
		a = qry(K[i], len + 1, K[i]);
		if(i != M - 1) b = qry(K[i], len + 1, K[i + 1]);
		else b = 0;
		my = a - b;
		rem += K[i];
		if(rem > a) return 0;
		rem -= my;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int qry(int, int, int, int, int, int)':
teams.cpp:14:39: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   14 |   return upper_bound(all(st[i]), val) - st[i].begin();
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(j < st[i * 2].size() && k < st[i * 2 + 1].size()){
      |         ~~^~~~~~~~~~~~~~~~~~
teams.cpp:31:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(j < st[i * 2].size() && k < st[i * 2 + 1].size()){
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~
teams.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (; j < st[i * 2].size(); j++) st[i].push_back(st[i * 2][j]);
      |          ~~^~~~~~~~~~~~~~~~~~
teams.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (; k < st[i * 2 + 1].size(); k++) st[i].push_back(st[i * 2 + 1][k]);
      |          ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17488 KB Output is correct
2 Correct 31 ms 17244 KB Output is correct
3 Correct 31 ms 17392 KB Output is correct
4 Correct 32 ms 19008 KB Output is correct
5 Correct 14 ms 15264 KB Output is correct
6 Correct 14 ms 15452 KB Output is correct
7 Incorrect 14 ms 15452 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17676 KB Output is correct
2 Correct 36 ms 17664 KB Output is correct
3 Correct 112 ms 20656 KB Output is correct
4 Correct 33 ms 19028 KB Output is correct
5 Correct 50 ms 15956 KB Output is correct
6 Correct 38 ms 16456 KB Output is correct
7 Incorrect 49 ms 16124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 83540 KB Output is correct
2 Correct 199 ms 83516 KB Output is correct
3 Correct 459 ms 89704 KB Output is correct
4 Correct 193 ms 90704 KB Output is correct
5 Correct 158 ms 74836 KB Output is correct
6 Correct 121 ms 74172 KB Output is correct
7 Incorrect 152 ms 74324 KB Output isn't correct
8 Halted 0 ms 0 KB -