Submission #50646

#	Time	Username	Problem	Language	Result	Execution time	Memory
50646		Mamnoon_Siam	Teams (IOI15_teams)	C++17	0 / 100	807 ms	59472 KiB

teams

#include "teams.h"
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

struct FenwickTree {
	vector<int> vals;
	vector<vector<int>> ft;
	FenwickTree() {}
	FenwickTree(vector<int> &v) {
		ft.assign(v.size() + 1, vector<int>());
		for(int i = 0; i < v.size(); i++) {
			for(int j = i + 1; j < ft.size(); j += j & -j) {
				ft[j].push_back(v[i]);
			}
		}
		for(int i = 0; i < ft.size(); i++) {
			sort(all(ft[i]));
		}
		vals = v;
		sort(all(vals));
	}
	int leq(int p, int val) {
		int ret = upper_bound(all(vals), val) - vals.begin();
		for(; p > 0; p -= p & -p) {
			ret -= (upper_bound(all(ft[p]), val) - ft[p].begin());
		} return ret;
	}
};

int n;
vector<int> L, R;
FenwickTree bit;

void init(int N, int A[], int B[]) {
	L.resize(N);
	R.resize(N);
	n = N;
	for(int i = 0; i < N; i++) {
		L[i] = A[i];
		R[i] = B[i];
	}
	vector<ii> temp;
	for(int i = 0; i < n; i++) {
		temp.push_back(ii(R[i], L[i]));
	}
	sort(all(temp));
	for(int i = 0; i < n; i++) {
		L[i] = temp[i].second;
		R[i] = temp[i].first;
	}
	bit = FenwickTree(L);
}

int can(int M, int K[]) {
	sort(K, K + M);
	int s = 0;
	for(int i = 0; i < M; i++)
		s += K[i];
	if(s > n) return 0;
	int carry = 0;
	for(int i = 0; i < M; i++) {
		int it = lower_bound(all(R), K[i]) - R.begin();
		int has = bit.leq(it, K[i]);
		int need = carry + K[i];
		if(has < need) return 0;
		if(i < M - 1) {
			int it_nxt = lower_bound(all(R), K[i + 1]) - R.begin();
			int has_nxt = bit.leq(it_nxt, K[i]);
			int mid = has - has_nxt;
			need -= mid;
			need = max(0, need);
			carry = need;
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int myrand(int, int)':
teams.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
teams.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
teams.cpp: In constructor 'FenwickTree::FenwickTree(std::vector<int>&)':
teams.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
teams.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i + 1; j < ft.size(); j += j & -j) {
                       ~~^~~~~~~~~~~
teams.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ft.size(); i++) {
                  ~~^~~~~~~~~~~
teams.cpp: In member function 'int FenwickTree::leq(int, int)':
teams.cpp:49:41: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int ret = upper_bound(all(vals), val) - vals.begin();
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:51:56: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
    ret -= (upper_bound(all(ft[p]), val) - ft[p].begin());
                                                        ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:88:38: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int it = lower_bound(all(R), K[i]) - R.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:93:47: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
    int it_nxt = lower_bound(all(R), K[i + 1]) - R.begin();
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23