Submission #1033078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033078		socpite	Teams (IOI15_teams)	C++17	77 / 100	2878 ms	524288 KiB

teams

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

const int maxn = 5e5+5;
const long long INF = 1e18;
const int blsz = 155;

vector<int> FW[maxn];
vector<int> d[maxn];

int pfx_all[maxn], sfx_all[maxn];
int L[maxn], R[maxn];
int dp[maxn];

vector<int> precalc[maxn];
vector<int> pos[maxn];

map<pair<int, int>, int> mp;

int n;

void add(int x, int y){
	for(x; x <= n; x += x&(-x)){
		int idx = lower_bound(d[x].begin(), d[x].end(), y) - d[x].begin();
		FW[x][idx]++;
	}
}

int gt(int x, int y){
	int re = 0;
	for(x; x > 0; x -= x&(-x)){
		int idx = upper_bound(d[x].begin(), d[x].end(), y) - d[x].begin() - 1;
		re += FW[x][idx];
	}
	return re;
}

int gt_gap(int l, int r){
	if(l > r)return 0;
	if(r-l < precalc[l].size())return precalc[l][r-l];
	if(mp.find({l, r}) != mp.end())return mp[{l, r}];
	int re = pfx_all[r] - gt(r, l-1);
	mp[{l, r}] = re; 
	return re;
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++){
		L[i] = A[i];
		R[i] = B[i];
		pos[R[i]].push_back(L[i]);
		for(int x = B[i]; x <= n; x += x&(-x))d[x].push_back(A[i]);
		pfx_all[B[i]]++;
		sfx_all[A[i]]++;
	}
	for(int i = 1; i <= n; i++){
		pfx_all[i] += pfx_all[i-1];
		sort(pos[i].begin(), pos[i].end());
		d[i].push_back(-1);
		sort(d[i].begin(), d[i].end());
		d[i].erase(unique(d[i].begin(), d[i].end()), d[i].end());
		FW[i].assign(d[i].size(), 0);
	}

	for(int i = 1; i <= n; i++){
		int crr = 0;
		for(int j = 0; j + i <= n && j < (i < blsz ? n : n/i); j++){
			crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i);
			precalc[i].push_back(crr);
		}
	}

	for(int i = n; i >= 1; i--)sfx_all[i] += sfx_all[i+1];
	for(int i = 0; i < n; i++)add(B[i], A[i]);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j < FW[i].size(); j++)FW[i][j] += FW[i][j-1];
	}
}

int can(int M, int K[]) {
	long long sum = 0;
	sort(K, K+M);
	vector<pair<int, int>> vec;
	for(int i = 0; i < M; i++){
		sum += K[i];
		if(vec.empty() || vec.back().first != K[i])vec.push_back({K[i], 1});
		else vec.back().second++;
	}
	if(sum > n)return 0;
	for(int i = 0; i < vec.size(); i++){
		dp[i] = vec[i].first*vec[i].second + pfx_all[vec[i].first-1];
		for(int j = 0; j < i; j++){
			dp[i] = max(dp[i], dp[j] + vec[i].first*vec[i].second + gt_gap(vec[j].first+1,vec[i].first-1));
		}
		sum -= vec[i].first*vec[i].second;
		if(dp[i] + sum > n)return 0;
		if(dp[i] + sfx_all[vec[i].first+1] > n)return 0;
	}
	return 1;
	// sum_segment - sum_M < 0 => bad
	// sum_segment = pfx_all - sumgap
	
}

Compilation message (stderr)

teams.cpp: In function 'void add(int, int)':
teams.cpp:24:6: warning: statement has no effect [-Wunused-value]
   24 |  for(x; x <= n; x += x&(-x)){
      |      ^
teams.cpp:25:54: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   25 |   int idx = lower_bound(d[x].begin(), d[x].end(), y) - d[x].begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp: In function 'int gt(int, int)':
teams.cpp:32:6: warning: statement has no effect [-Wunused-value]
   32 |  for(x; x > 0; x -= x&(-x)){
      |      ^
teams.cpp:33:69: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   33 |   int idx = upper_bound(d[x].begin(), d[x].end(), y) - d[x].begin() - 1;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int gt_gap(int, int)':
teams.cpp:41:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  if(r-l < precalc[l].size())return precalc[l][r-l];
      |     ~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:70:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   70 |    crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i);
      |                                                                           ^
teams.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int j = 1; j < FW[i].size(); j++)FW[i][j] += FW[i][j-1];
      |                  ~~^~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < vec.size(); i++){
      |                 ~~^~~~~~~~~~~~

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