Submission #73580

#	Time	Username	Problem	Language	Result	Execution time	Memory
73580		funcsr	Holiday (IOI14_holiday)	C++17	24 / 100	21 ms	4056 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;
//#define MAX_N (1<<17)
#define MAX_N (1<<12)
struct SegTree {
  const int num;
  const long long sum;
  SegTree *left = NULL, *right = NULL;
  SegTree(int n, long long s) : num(n), sum(s) { V++; }

  long long rsum(int n, int l=0, int r=MAX_N) {
    if (n == 0) return 0;
    if (r-l==1) return sum;

    long long s = 0;
    if (right==NULL || n >= right->num) {
      if (right) {
        n -= right->num;
        s += right->sum;
      }
      if (left) s += left->rsum(n, l, (l+r)/2);
    }
    else {
      if (right) s += right->rsum(n, (l+r)/2);
    }
    return s;
  }
  SegTree *update(int p, int val, int l=0, int r=MAX_N) {
    if (r-l == 1) {
      SegTree *ret = new SegTree(1, val);
      return ret;
    }

    int mid = (l+r)/2;

    SegTree *a = left, *b = right;
    if (p < mid) {
      if (!left) left = new SegTree(0, 0);
      a = left->update(p, val, l, mid);
    }
    else {
      if (!right) right = new SegTree(0, 0);
      b = right->update(p, val, mid, r);
    }

    SegTree *ret = new SegTree(num+1, sum+val);
    ret->left = a;
    ret->right = b;
    return ret;
  }
};
int D, W;
SegTree *seg[100001];

inline long long f(int d, int e) {
  if (d <= e*W) return 0;
  assert(seg[e] != NULL);
  return seg[e]->rsum(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] = new SegTree(0, 0);
  rep(i, A.size()) seg[i+1] = seg[i]->update(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]);
  }
  for (int i=A.size(); i>=0; i--) delete seg[i];
  return ret;
}

long long findMaxAttraction(int N, int S, int DD, int A[]) {
  assert(N<=3000);
  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 '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:95: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:98:3: note: in expansion of macro 'rep'
   rep(i, A.size()) seg[i+1] = seg[i]->update(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: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53