Submission #286691

#	Time	Username	Problem	Language	Result	Execution time	Memory
286691		Atill83	Teams (IOI15_teams)	C++14	77 / 100	2191 ms	165956 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int MAXN = (int) 5e5 + 5;

vector<ll> t[4*MAXN];

void add(int v, int tl, int tr, int val, int pos){
	if(tl == tr){
		t[v].push_back(val);
	}else{
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			add(2*v, tl, tm, val, pos);
		}else{
			add(2*v+1, tm + 1, tr, val, pos);
		}
		t[v].push_back(val);
	}
}

ll que(int v, int tl, int tr, int l, int r, int val){
	if(l > r) return 0;
	if(tl == l && tr == r){
		return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
	}else{
		int tm = (tl + tr) / 2;
		return que(2*v, tl, tm, l, min(tm, r), val) + que(2*v+1, tm + 1, tr, max(tm + 1, l), r, val);
	}
}



void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < N; i++){
		add(1, 1, N, B[i], A[i]);
	}
	for(int i = 1; i < 4*MAXN; i++) sort(t[i].begin(), t[i].end());
}
ll dp[MAXN];

int can(int M, int K[]) {
	int N = n;
	sort(K, K + M);
	vector<ll> lst;
	dp[0] = que(1, 1, N , 1, K[0], K[0]) - K[0];
	if(dp[0] < 0) return 0;
	lst.push_back(0);
	for(int i = 1; i < M; i++){
		dp[i] = que(1, 1, N, 1, K[i], K[i]) - K[i];
		while(lst.size() > 1){
			int cur = lst.back();
			lst.pop_back();
			ll deg1 = dp[cur] + que(1, 1, N, K[cur] + 1, K[i], K[i]);
			ll deg2 = dp[lst.back()] + que(1, 1, N , K[lst.back()] + 1, K[i], K[i]);
			if(deg2 > deg1){
				lst.push_back(cur);
				break;
			}
		}
		dp[i] = min(dp[i], dp[lst.back()] + que(1, 1, N, K[lst.back()] + 1, K[i], K[i]) - K[i]);
		lst.push_back(i);
		if(dp[i] < 0) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:55:22: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |    int cur = lst.back();
      |              ~~~~~~~~^~

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