Submission #1035833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035833		d4xn	Holiday (IOI14_holiday)	C++17	7 / 100	79 ms	65536 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5;

struct node {
  int cnt, sum;
  node* L;
  node* R;

  node() {
    cnt = sum = 0;
    L = R = nullptr;
  }
};

int n, s, d, a[N];
pair<int, int> b[N];
node* root[N];

node* merge(node* x, node* y) {
  node* z = new node();
  z->cnt = x->cnt + y->cnt;
  z->sum = x->sum + y->sum;
  return z;
}

node* build(int l=0, int r=n-1) {
  node* p = new node();

  if (l == r) {
    if (l == b[0].second) {
      p->cnt = 1;
      p->sum = b[0].first;
    }
    return p;
  }

  int mid = (l+r) >> 1;
  p->L = build(l, mid);
  p->R = build(mid+1, r); 

  p->cnt = p->L->cnt + p->R->cnt;
  p->sum = p->L->sum + p->R->sum;  

  return p;
}

node* update(int idx, int x, node* root, int l=0, int r=n-1) {
  node* p = new node();

  if (l == r) {
    p->cnt = 1;
    p->sum = x;
    return p;
  }

  int mid = (l+r) >> 1;
  if (idx <= mid) {
    p->L = update(idx, x, root->L, l, mid);
    p->R = root->R;
  }
  else {
    p->L = root->L;
    p->R = update(idx, x, root->R, mid+1, r);
  }

  p->cnt = p->L->cnt + p->R->cnt;
  p->sum = p->L->sum + p->R->sum;  

  return p;
}

node* query(int a, int b, node* root, int l=0, int r=n-1) {
  if (a <= l && r <= b) {
    return root;
  }

  int mid = (l+r) >> 1;
  if (b <= mid) {
    return query(a, b, root->L, l, mid);
  }
  else if (mid+1 <= a) {
    return query(a, b, root->R, mid+1, r);
  }
  else {
    return merge(query(a, b, root->L, l, mid), query(a, b, root->R, mid+1, r));
  }
}

int c(int a, int b) {
  int x = b-a + min(s-a, b-s);
  if (x >= d) return 0;

  x = min(d-x, b-a+1);

  int l = 0;
  int r = n-1 - (b-a+1 - x);
  while (l < r) {
    int mid = (l+r) >> 1;

    if (query(a, b, root[mid])->cnt >= x) r = mid;
    else l = mid+1;
  }

  return query(a, b, root[l])->sum;
}

int findMaxAttraction(signed N, signed S, signed D, signed attraction[]) {
    n = N;
    s = S;
    d = D;
    for (int i = 0; i < n; i++) {
        a[i] = attraction[i];
        b[i] = make_pair(a[i], i);
    }
    sort(b, b+n);
    reverse(b, b+n);

    root[0] = build();
    for (int i = 1; i < n; i++) {
        root[i] = update(b[i].second, b[i].first, root[i-1]);
    }
    
    int ans = 0;
    for (int i = 0; i <= s; i++) {
        for (int j = s; j < n; j++) {
            ans = max(ans, c(i, j));
        }
    }

    return ans;
}

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