Submission #43615

#	Time	Username	Problem	Language	Result	Execution time	Memory
43615		szawinis	Teams (IOI15_teams)	C++14	100 / 100	2309 ms	357936 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5+10;

int n, used_root, root[N];
vector<int> ls[N], t, nxtl, nxtr;
int newLeaf(int v) {
	t.push_back(v);
	nxtl.push_back(-1);
	nxtr.push_back(-1);
	return t.size()-1;
}
int newPar(int l, int r) {
	t.push_back(t[l] + t[r]);
	nxtl.push_back(l);
	nxtr.push_back(r);
	return t.size()-1;
}
int build(int l = 0, int r = N-1) {
	if(l == r) return newLeaf(0);
	int mid = l+r >> 1;
	return newPar(build(l, mid), build(mid+1, r));
}
int update(int i, int targ, int l = 0, int r = N-1) {
	if(l == r) return newLeaf(t[i] + 1);
	int mid = l+r >> 1;
	if(targ <= mid) return newPar(update(nxtl[i], targ, l, mid), nxtr[i]);
	else return newPar(nxtl[i], update(nxtr[i], targ, mid+1, r));
}
int erase(int i, int zeroi, int targ, int l = 0, int r = N-1) {
	if(r <= targ) return zeroi;
	if(l > targ) return i;
	int mid = l+r >> 1;
	return newPar(erase(nxtl[i], nxtl[zeroi], targ, l, mid), erase(nxtr[i], nxtr[zeroi], targ, mid+1, r));
}
int query(int avail, int used, int k, int l = 0, int r = N-1) {// returns index of new used root, but -1 if failure
	if(t[avail] - t[used] < k) return -1;
	if(l == r) return newLeaf(t[used] + k);
	int cntl = t[nxtl[avail]] - t[nxtl[used]];
	int mid = l+r >> 1;
	if(cntl >= k)
		return newPar(query(nxtl[avail], nxtl[used], k, l, mid), nxtr[used]);
	else
		return newPar(nxtl[avail], query(nxtr[avail], nxtr[used], k - cntl, mid+1, r));
}
int get(int i, int tl, int tr, int l = 0, int r = N-1) {
	if(r < tl || l > tr) return 0;
	if(l >= tl && r <= tr) return t[i];
	int mid = l+r >> 1, ret = 0;
	if(nxtl[i] != -1) ret += get(nxtl[i], tl, tr, l, mid);
	if(nxtr[i] != -1) ret += get(nxtr[i], tl, tr, mid+1, r);
	return ret;
}
void init(int _n, int a[], int b[]) {
	n = _n;
	for(int i = 0; i < n; i++) ls[a[i]].push_back(b[i]);
	root[0] = build();
	for(int i = 1; i <= n; i++) { // direction of iteration is insignificant
		root[i] = erase(root[i-1], root[0], i-1);
		for(int j = 0; j < ls[i].size(); j++) root[i] = update(root[i], ls[i][j]);
	}
	used_root = build();
}
int can(int m, int k[]) {
	sort(k, k+m);
	int used = used_root;
	for(int i = 0; i < m; i++) {
		used = erase(used, root[0], k[i]-1);
		used = query(root[k[i]], used, k[i]);
		if(used == -1) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int newLeaf(int)':
teams.cpp:13:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return t.size()-1;
                  ^
teams.cpp: In function 'int newPar(int, int)':
teams.cpp:19:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return t.size()-1;
                  ^
teams.cpp: In function 'int build(int, int)':
teams.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
teams.cpp: In function 'int update(int, int, int, int)':
teams.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
teams.cpp: In function 'int erase(int, int, int, int, int)':
teams.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1, ret = 0;
             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ls[i].size(); j++) root[i] = update(root[i], ls[i][j]);
                    ^

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