Submission #172361

#	Time	Username	Problem	Language	Result	Execution time	Memory
172361		gs18103	Teams (IOI15_teams)	C++14	0 / 100	971 ms	213820 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 505050;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;

struct Node {
	int l, r, val;
	Node(int l, int r, int val) : l(l), r(r), val(val) {}
};

int n, root[MAX];
vector <Node> tree;
pii arr[MAX];

void expand_tree(int s, int e, int k, int pnd, int cnd) {
	tree[cnd].val = tree[pnd].val + 1;
	if(s == e) return;
	int m = s + e >> 1;
	if(k <= m) {
		tree[cnd].r = tree[pnd].r;
		tree[cnd].l = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
	}
	else {
		tree[cnd].l = tree[pnd].l;
		tree[cnd].r = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
	}
}

int cal(int s, int e, int l, int r, int pnd, int cnd) {
	if(s > r || e < l) return 0;
	if(s >= l && e <= r) return tree[cnd].val - tree[pnd].val;
	int m = s + e >> 1;
	return cal(s, m, l, r, tree[pnd].l, tree[cnd].l)
		+ cal(m+1, e, l, r, tree[pnd].r, tree[cnd].r);
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++) {
		arr[i] = make_pair(B[i], A[i]);
	}
	sort(arr, arr+n);
	tree.eb(0, 0, 0);
	for(int i = 0; i < n; i++) {
		root[i+1] = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(1, n, arr[i].se, root[i], root[i+1]);
	}
	return;
}

int can(int M, int K[]) {
	ll temp = 0;
	for(int i = 0; i < M; i++) temp += K[i];
	if(temp > n) return 0;
	sort(K, K+M, [](int a, int b){return a > b;});
	int pre = n + 1, cnt = 0, sum = 0;
	for(int i = 0; i < M; i++) {
		sum += K[i];
		int nxt = lower_bound(arr, arr+n, make_pair(K[i], 0))-arr+1;
		cnt += cal(1, n, 1, K[i], root[nxt-1], root[pre-1]);
		if(cnt < sum) return 0;
		pre = nxt;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:21:30: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:12: note: shadowed declaration is here
  int l, r, val;
            ^~~
teams.cpp:21:30: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:9: note: shadowed declaration is here
  int l, r, val;
         ^
teams.cpp:21:30: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:6: note: shadowed declaration is here
  int l, r, val;
      ^
teams.cpp: In function 'void expand_tree(int, int, int, int, int)':
teams.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp:34:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].l = tree.size();
                 ~~~~~~~~~^~
teams.cpp:40:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].r = tree.size();
                 ~~~~~~~~~^~
teams.cpp: In function 'int cal(int, int, int, int, int, int)':
teams.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:24: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   root[i+1] = tree.size();
               ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:77:60: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int nxt = lower_bound(arr, arr+n, make_pair(K[i], 0))-arr+1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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