Submission #154340

#	Time	Username	Problem	Language	Result	Execution time	Memory
154340		catalystgma	Holiday (IOI14_holiday)	C++11	47 / 100	666 ms	7264 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define pli pair<lll,int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxn 100000
#define maxf 100

using namespace std;

int n;
int v[maxn+5], fv[maxf+5], wh[maxn+5];
pli aint[4*maxn+5];///fi=suma itv,se=nr de !=0 pe itv !!nu=0pt ca aintul nu e construit corect la inceput
///.se==0 cand ar tb sa fie >0
pii u[maxn+5];///fi=v[i],se=i
lll ans;

void umax (lll &a, lll b) { a = max(a,b); }

void update (int p, pii itv, int ind) {
  if (wh[ind] < itv.fi || itv.se < wh[ind]) return;
  if (itv.fi == itv.se) {
    if (aint[p].fi == 0) aint[p] = {1LL*v[ind], 1};
    else aint[p] = {0, 0};
    return;
  }
  int mid = (itv.fi + itv.se) / 2;
  update (p*2, {itv.fi, mid}, ind);
  update (p*2+1, {mid+1, itv.se}, ind);
  aint[p] = {aint[p*2].fi+aint[p*2+1].fi, aint[p*2].se+aint[p*2+1].se};
}

void preupdate (int ind) { update(1, {1,n}, ind); }

lll q_query;///vreau suma celor mai mari k nr din aint
void query (int p, pii itv, int cat) { ///iau din itv cele mai mari cat nr
  if (cat <= 0) return;
  if (cat >= aint[p].se) { q_query += aint[p].fi; return; }
  if (itv.fi == itv.se) return;
  int mid = (itv.fi + itv.se) / 2;
  if (cat > aint[p*2].se) {
    query (p*2, {itv.fi, mid}, aint[p*2].se);
    query (p*2+1, {mid+1, itv.se}, cat-aint[p*2].se);
  } else query (p*2, {itv.fi, mid}, cat);
}

lll prequery (int cat) {
  q_query = 0;
  cat = min(cat, aint[1].se);
  query (1, {1,n}, cat);
  return q_query;
}

lll biggest (int rem) {
  int nr; lll cur = 0;
  for (nr = maxf; nr > 0 && rem > 0; nr--)
    if (rem > fv[nr]) {
      cur += 1LL * fv[nr] * nr;
      rem -= fv[nr];
    } else {
      cur += 1LL * rem * nr;
      rem = 0;
    }
  return cur;
}

int minpasi (int start, int a, int b) { return b-a+min(start-a, b-start); }

bool cmp (pii a, pii b) {
  if (a.fi != b.fi) return a.fi > b.fi;
  return a.se < b.se;
}

lll findMaxAttraction (int n_, int start_, int d_, int* v_) {
  n = n_;
  int start = start_, d = d_;
  int i, j, z;
  if (start == 0 && n > 3000) {
    for (i = 0; i < n; i++) v[i] = v_[i];
    for (j = 0; j < n; j++) {
      fv[v[j]]++;
      umax(ans, biggest(d-j));
    }
  } else {
    start++;///!!!!
    for (i = 1; i <= n; i++) v[i] = v_[i-1];
    for (i = 1; i <= n; i++) u[i] = {v[i], i};
    sort(u+1, u+n+1, cmp);
    for (i = 1; i <= n; i++) wh[u[i].se] = i;
    int a, b;
    for (a = start; a >= 1; a--) {
      for (b = start; b <= n; b++) {
        preupdate(b);
        umax (ans, prequery(d-minpasi(start, a, b)));
      }
      for (b = n; b >= start; b--) preupdate(b);
      if (a > 1) preupdate(a-1);
    }
  }
  return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:94:13: warning: unused variable 'z' [-Wunused-variable]
   int i, j, z;
             ^

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