Submission #994994

#	Time	Username	Problem	Language	Result	Execution time	Memory
994994		fuad27	Holiday (IOI14_holiday)	C++17	47 / 100	88 ms	65536 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")



// https://codeforces.com/blog/entry/103178?#comment-915863
	struct Node {
		long long sum;
		int cnt;
		int lCh, rCh;//children, indexes into `tree`
	};
vector<Node> tree;
struct sum_kth_smallest {
 
vector<int> roots;
	int mn, mx;
   sum_kth_smallest(){}
	sum_kth_smallest(const vector<int>& arr) : mn(INT_MAX), mx(INT_MIN), roots(arr.size() + 1, 0) {
		tree.push_back({0, 0, 0}); //acts as null
		for (int val : arr) mn = min(mn, val), mx = max(mx, val);
		for (int i = 0; i < (int)arr.size(); i++)
			roots[i + 1] = update(roots[i], mn, mx, arr[i]);
	}
	int update(int v, int tl, int tr, int idx) {
		if (tl == tr) {
			tree.push_back({tree[v].sum + tl, tree[v].cnt + 1, 0, 0});
			return tree.size() - 1;
		}
		int tm = tl + (tr - tl) / 2;
		int lCh = tree[v].lCh;
		int rCh = tree[v].rCh;
		if (idx <= tm)
			lCh = update(lCh, tl, tm, idx);
		else
			rCh = update(rCh, tm + 1, tr, idx);
		tree.push_back({tree[lCh].sum + tree[rCh].sum, tree[lCh].cnt + tree[rCh].cnt, lCh, rCh});
		return tree.size() - 1;
	}
 
 
	/* find kth smallest number among arr[l], arr[l+1], ..., arr[r]
	 * k is 1-based, so find_kth(l,r,1) returns the min
	 */
	int query(int l, int r, int k) const {
//		assert(1 <= k && k <= r - l + 1); //note this condition implies L <= R
//		assert(0 <= l && r + 1 < (int)roots.size());
		return query(roots[l], roots[r + 1], mn, mx, k);
	}
	int query(int vl, int vr, int tl, int tr, int k) const {
		if (tl == tr)
			return tl;
		int tm = tl + (tr - tl) / 2;
		int left_count = tree[tree[vr].lCh].cnt - tree[tree[vl].lCh].cnt;
		if (left_count >= k) return query(tree[vl].lCh, tree[vr].lCh, tl, tm, k);
		return query(tree[vl].rCh, tree[vr].rCh, tm + 1, tr, k - left_count);
	}
 
	/* find **sum** of k smallest numbers among arr[l], arr[l+1], ..., arr[r]
	 * k is 1-based, so find_kth(l,r,1) returns the min
	 */
	long long query_sum(int l, int r, int k) const {
    if(k<=0)return 0;
    k=min(k, (r-l+1));
    if(l>r)return 0;
//		assert(1 <= k && k <= r - l + 1); //note this condition implies L <= R
//		assert(0 <= l && r + 1 < (int)roots.size());
		return query_sum(roots[l], roots[r + 1], mn, mx, k);
	}
	long long  query_sum(int vl, int vr, int tl, int tr, int k) const {
		if (tl == tr)
			return 1LL * tl * k;
		int tm = tl + (tr - tl) / 2;
		int left_count = tree[tree[vr].lCh].cnt - tree[tree[vl].lCh].cnt;
		long long left_sum = tree[tree[vr].lCh].sum - tree[tree[vl].lCh].sum;
		if (left_count >= k) return query_sum(tree[vl].lCh, tree[vr].lCh, tl, tm, k);
		return left_sum + query_sum(tree[vl].rCh, tree[vr].rCh, tm + 1, tr, k - left_count);
	}
};
sum_kth_smallest sg;

int n, start, d;
vector<int> attraction;
vector<long long> F, S, F2, S2;

long long get(int l, int r, int k) {
  return -sg.query_sum(l, r, k);
}

void calcf1(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    long long val = get(start, i, mid-abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  F[mid] = res;
  calcf1(l, mid-1, pl, opt);
  calcf1(mid+1, r, opt, pr);
}
void calcs1(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    long long val = get(start, i, mid-2*abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  S[mid] = res;
  calcs1(l, mid-1, pl, opt);
  calcs1(mid+1, r, opt, pr);
}
//
void calcf2(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    long long val = get(i, start-1, mid-abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  F2[mid] = res;
  calcf2(l, mid-1, opt, pr);
  calcf2(mid+1, r, pl, opt);
}
void calcs2(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    long long val = get(i,start-1, mid-2*abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  S2[mid] = res;
  calcs2(l, mid-1, opt, pr);
  calcs2(mid+1, r, pl, opt);
}
long long int findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
  n=_n;
  start=_start;
  d=_d;
  S.resize(d+1);
  F.resize(d+1);
  S2.resize(d+1);
  F2.resize(d+1);
  attraction=vector<int>(_attraction, _attraction+_n);
  for(int &i:attraction)i*=-1;
  sg=sum_kth_smallest(attraction);
  for(int &i:attraction)i*=-1;
  calcf1(1, _d, _start, _n-1);
  calcs1(1, _d, _start, _n-1);
  calcf2(1, _d, 0, _start-1);
  calcs2(1, _d, 0, _start-1);
  long long res=0;
  for(int i = 0;i<=d;i++) {
    res=max(res, F[i]+S2[d-i]);
    res=max(res, S[i]+F2[d-i]);
  }
  return res;
}

Compilation message (stderr)

holiday.cpp: In constructor 'sum_kth_smallest::sum_kth_smallest(const std::vector<int>&)':
holiday.cpp:18:10: warning: 'sum_kth_smallest::mx' will be initialized after [-Wreorder]
   18 |  int mn, mx;
      |          ^~
holiday.cpp:17:13: warning:   'std::vector<int> sum_kth_smallest::roots' [-Wreorder]
   17 | vector<int> roots;
      |             ^~~~~
holiday.cpp:20:2: warning:   when initialized here [-Wreorder]
   20 |  sum_kth_smallest(const vector<int>& arr) : mn(INT_MAX), mx(INT_MIN), roots(arr.size() + 1, 0) {
      |  ^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53