Submission #916171

#	Time	Username	Problem	Language	Result	Execution time	Memory
916171		Trisanu_Das	Teams (IOI15_teams)	C++17	77 / 100	1475 ms	125668 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = (int) 5e5 + 5;
 
vector<int> 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);
	}
}
 
int 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());
}
int dp[MAXN];
 
int can(int M, int K[]) {
	int N = n;
	sort(K, K + M);
	vector<int> 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();
			int deg1 = dp[cur] + que(1, 1, N, K[cur] + 1, K[i], K[i]);
			int 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 que(int, int, int, int, int, int)':
teams.cpp:26:21: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   26 |   return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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