Submission #1033112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033112		socpite	Teams (IOI15_teams)	C++17	77 / 100	1144 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 = 100;

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;

struct node{
	node *lc, *rc;
	int sum;
	node(int _sum = 0): sum(_sum), lc(nullptr), rc(nullptr){};
	void build(int l = 1, int r = n){
		if(l == r)return;
		lc = new node();
		rc = new node();
		int mid = (l+r)>>1;
		lc->build(l, mid);
		rc->build(mid+1, r);
	}
	void upd(node &old_tree, int pos, int l = 1, int r = n){
		sum = old_tree.sum + 1;
		if(l == r)return;
		int mid = (l+r)>>1;
		if(pos <= mid){
			rc = old_tree.rc;
			lc = new node();
			lc->upd(*old_tree.lc, pos, l, mid);
		}
		else {
			lc = old_tree.lc;
			rc = new node();
			rc->upd(*old_tree.rc, pos, mid+1, r);
		}
	}
	int query(int pos, int l = 1, int r = n){
		if(l == r)return sum;
		int mid = (l+r)>>1;
		if(pos <= mid)return lc->query(pos, l, mid);
		else return rc->query(pos, mid+1, r) + lc->sum;
	}
};

vector<node> rt;
int rtpos[maxn];

int gt(int a, int b){
	if(b == 0)return 0;
	return rt[rtpos[a]].query(b);
}

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 < 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];

	rt.push_back(node());
	rt.back().build();
	for(int i = 1; i <= n; i++){
		for(auto v: pos[i]){
			node nw;
			nw.upd(rt.back(), v);
			rt.push_back(nw);
		}
		rtpos[i] = rt.size()-1;
	}

	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 constructor 'node::node(int)':
teams.cpp:25:6: warning: 'node::sum' will be initialized after [-Wreorder]
   25 |  int sum;
      |      ^~~
teams.cpp:24:8: warning:   'node* node::lc' [-Wreorder]
   24 |  node *lc, *rc;
      |        ^~
teams.cpp:26:2: warning:   when initialized here [-Wreorder]
   26 |  node(int _sum = 0): sum(_sum), lc(nullptr), rc(nullptr){};
      |  ^~~~
teams.cpp: In member function 'void node::upd(node&, int, int, int)':
teams.cpp:35:31: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   35 |  void upd(node &old_tree, int pos, int l = 1, int r = n){
      |                           ~~~~^~~
teams.cpp:17:13: note: shadowed declaration is here
   17 | vector<int> pos[maxn];
      |             ^~~
teams.cpp: In member function 'int node::query(int, int, int)':
teams.cpp:50:16: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   50 |  int query(int pos, int l = 1, int r = n){
      |            ~~~~^~~
teams.cpp:17:13: note: shadowed declaration is here
   17 | vector<int> pos[maxn];
      |             ^~~
teams.cpp: In function 'int gt_gap(int, int)':
teams.cpp:68:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  if(r-l < precalc[l].size())return precalc[l][r-l];
      |     ~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:97:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   97 |    crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i);
      |                                                                           ^
teams.cpp:112:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  112 |   rtpos[i] = rt.size()-1;
      |              ~~~~~~~~~^~
teams.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   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:130: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]
  130 |  for(int i = 0; i < vec.size(); i++){
      |                 ~~^~~~~~~~~~~~

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