Submission #73605

#	Time	Username	Problem	Language	Result	Execution time	Memory
73605		funcsr	Holiday (IOI14_holiday)	C++17	100 / 100	974 ms	56000 KiB

holiday

#include "holiday.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)
using namespace std;
typedef pair<int, int> P;

int V=0;
const int MAX_V = (int)(18*100010);
struct SegTree;
SegTree *alloc(int n, long long v);
//#define MAX_N (1<<17)
const int MAX_N = 100001;
struct SegTree {
  int num;
  long long sum;
  int left = -1, right = -1;
  SegTree(int n, long long s) : num(n), sum(s) {}
  SegTree() : num(0), sum(0LL) {}
};

SegTree pool[MAX_V];
SegTree *alloc(int n, long long v) {
  assert(V<MAX_V);
  pool[V].num=n;
  pool[V].sum=v;
  pool[V].left = -1;
  pool[V].right = -1;
  return &pool[V++];
}

inline SegTree *left(SegTree *seg) { return seg->left==-1?NULL:&pool[seg->left]; }
inline SegTree *right(SegTree *seg) { return seg->right==-1?NULL:&pool[seg->right]; }

long long rsum(SegTree *seg, int n, int l=0, int r=MAX_N) {
  if (n == 0) return 0;
  if (r-l==1) return seg?seg->sum:0;

  long long s = 0;
  SegTree *rg = right(seg);
  if (rg == NULL || n >= rg->num) {
    if (rg) n -= rg->num, s += rg->sum;
    if (left(seg)) s += rsum(left(seg), n, l, (l+r)/2);
  }
  else {
    if (right(seg)) s += rsum(right(seg), n, (l+r)/2, r);
  }
  return s;
}

int update(SegTree *seg, int p, int val, int l=0, int r=MAX_N) {
  if (r-l == 1) {
    int id = V;
    SegTree *ret = alloc(1, val);
    return id;
  }

  int mid = (l+r)/2;
  int a = -1, b = -1;
  if (seg) a = seg->left, b = seg->right;
  if (p < mid) a = update(a==-1?NULL:&pool[a], p, val, l, mid);
  else b = update(b==-1?NULL:&pool[b], p, val, mid, r);

  int id = V;
  SegTree *ret = alloc((seg==NULL?0:seg->num)+1, (seg==NULL?0:seg->sum)+val);
  ret->left = a;
  ret->right = b;
  return id;
}


int D, W;
SegTree *seg[100001];

inline long long f(int d, int e) {
  if (d <= e*W) return 0;
  return rsum(seg[e], d-e*W);
}
int best(int x, int bottom, int top) {
  pair<long long, int> mp = make_pair(-1, -1);
  for (int i=bottom; i<=top; i++) mp = max(mp, make_pair(f(x, i), -i));
  return -mp._2;
}

void solve(int l, int r, int bottom, int top, vector<long long> &ret) {
  if (l > r) return;
  if (l == r) {
    ret[l] = best(l, bottom, top);
    return;
  }
  int mid = (l+r)/2;
  int q = ret[mid] = best(mid, bottom, top);
  solve(l, mid-1, bottom, q, ret);
  solve(mid+1, r, q, top, ret);
}

vector<vector<long long> > solve(vector<int> &A) {
  vector<P> ps;
  rep(i, A.size()) ps.pb(P(A[i], i));
  sort(all(ps));
  seg[0] = alloc(0, 0);
  rep(i, A.size()) seg[i+1] = &pool[update(seg[i], index(ps, P(A[i], i)), A[i])];

  vector<vector<long long> > ret(2, vector<long long>(D+1, 0));
  for (W=1; W<=2; W++) {
    solve(0, D, 0, A.size(), ret[W-1]);
    rep(i, D+1) ret[W-1][i] = f(i, ret[W-1][i]);
  }
  V=0;
  return ret;
}

long long findMaxAttraction(int N, int S, int DD, int A[]) {
  D = DD;
  vector<int> left, right;
  rep(i, S) left.pb(A[i]);
  for (int i=S+1; i<N; i++) right.pb(A[i]);
  reverse(all(left));

  vector<vector<long long> > dpL = solve(left);
  vector<vector<long long> > dpR = solve(right);
  //cout<<"V="<<V<<"\n";


  long long m = 0;
  rep(w, 2) {
    rep(i, D+1) m = max(m, dpL[w][i]+dpR[w^1][D-i]);
    rep(i, D) m = max(m, dpL[w][i]+dpR[w^1][D-i-1]+A[S]);
  }
  return m;
}

Compilation message (stderr)

holiday.cpp: In function 'int update(SegTree*, int, int, int, int)':
holiday.cpp:63:14: warning: unused variable 'ret' [-Wunused-variable]
     SegTree *ret = alloc(1, val);
              ^~~
holiday.cpp: In function 'std::vector<std::vector<long long int> > solve(std::vector<int>&)':
holiday.cpp:6:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
holiday.cpp:108:3: note: in expansion of macro 'rep'
   rep(i, A.size()) ps.pb(P(A[i], i));
   ^~~
holiday.cpp:6:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
holiday.cpp:111:3: note: in expansion of macro 'rep'
   rep(i, A.size()) seg[i+1] = &pool[update(seg[i], index(ps, P(A[i], i)), A[i])];
   ^~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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