Submission #995006

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

holiday

    #include"holiday.h"
    #include <bits/stdc++.h>
    using namespace std;
     
     
     
    // https://codeforces.com/blog/entry/103178?#comment-915863
    	struct Node {
    		long long sum;
    		long long cnt;
    		long long lCh, rCh;//children, indexes long longo `tree`
    	};
    vector<Node> tree;
    struct sum_kth_smallest {
     
    vector<long long> roots;
    	long long mn, mx;
       sum_kth_smallest(){}
    	sum_kth_smallest(const vector<long long>& arr) : mn(INT_MAX), mx(INT_MIN), roots(arr.size() + 1, 0) {
    		tree.push_back({0, 0, 0}); //acts as null
    		for (long long val : arr) mn = min(mn, val), mx = max(mx, val);
    		for (long long i = 0; i < (long long)arr.size(); i++)
    			roots[i + 1] = update(roots[i], mn, mx, arr[i]);
    	}
    	long long update(long long v, long long tl, long long tr, long long idx) {
    		if (tl == tr) {
    			tree.push_back({tree[v].sum + tl, tree[v].cnt + 1, 0, 0});
    			return tree.size() - 1;
    		}
    		long long tm = tl + (tr - tl) / 2;
    		long long lCh = tree[v].lCh;
    		long long 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
    	 */
    	long long query(long long l, long long r, long long k) const {
    //		assert(1 <= k && k <= r - l + 1); //note this condition implies L <= R
    //		assert(0 <= l && r + 1 < (long long)roots.size());
    		return query(roots[l], roots[r + 1], mn, mx, k);
    	}
    	long long query(long long vl, long long vr, long long tl, long long tr, long long k) const {
    		if (tl == tr)
    			return tl;
    		long long tm = tl + (tr - tl) / 2;
    		long long 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(long long l, long long r, long long 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 < (long long)roots.size());
    		return query_sum(roots[l], roots[r + 1], mn, mx, k);
    	}
    	long long  query_sum(long long vl, long long vr, long long tl, long long tr, long long k) const {
    		if (tl == tr)
    			return 1LL * tl * k;
    		long long tm = tl + (tr - tl) / 2;
    		long long 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;
     
    long long n, start, d;
    vector<long long> attraction;
    vector<long long> F, S, F2, S2;
     
    long long get(long long l, long long r, long long k) {
      return -sg.query_sum(l, r, k);
    }
     
    void calcf1(long long l, long long r, long long pl, long long pr) {
      if(l>r)return;
      long long mid = (l+r)/2;
      long long res=0;
      long long opt = pl;
      for(long long 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(long long l, long long r, long long pl, long long pr) {
      if(l>r)return;
      long long mid = (l+r)/2;
      long long res=0;
      long long opt = pl;
      for(long long 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(long long l, long long r, long long pl, long long pr) {
      if(l>r)return;
      long long mid = (l+r)/2;
      long long res=0;
      long long opt = pl;
      for(long long 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(long long l, long long r, long long pl, long long pr) {
      if(l>r)return;
      long long mid = (l+r)/2;
      long long res=0;
      long long opt = pl;
      for(long long 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<long long>(_attraction, _attraction+_n);
      for(long long &i:attraction)i*=-1;
      sg=sum_kth_smallest(attraction);
      for(long long &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(long long 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<long long int>&)':
holiday.cpp:17:20: warning: 'sum_kth_smallest::mx' will be initialized after [-Wreorder]
   17 |      long long mn, mx;
      |                    ^~
holiday.cpp:16:23: warning:   'std::vector<long long int> sum_kth_smallest::roots' [-Wreorder]
   16 |     vector<long long> roots;
      |                       ^~~~~
holiday.cpp:19:6: warning:   when initialized here [-Wreorder]
   19 |      sum_kth_smallest(const vector<long long>& 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