Submission #299207

#	Time	Username	Problem	Language	Result	Execution time	Memory
299207		erd1	Holiday (IOI14_holiday)	C++14	0 / 100	17 ms	1280 KiB

holiday

#include"holiday.h"

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;

struct node{
  node *L = 0, *R = 0;
  int key;
  lld sum;
  int val, cnt = 1;
  node(int v) : key(rand()), sum(v), val(v) { }
  void up(){ sum = val, cnt = 1; if(L)sum += L->sum, cnt += L->cnt; if(R)sum += R->sum, cnt += R->cnt; }
  pair<node*, node*> splitVal(int s){
    if(val < s){
      if(!L)return{nullptr, this};
      auto p = L->splitVal(s);
      L = p.ss; up();
      return {p.ff, this};
    }else{
      if(!R)return{this, nullptr};
      auto p = R->splitVal(s);
      R = p.ff; up();
      return {this, p.ss};
    }
  }
  pair<node*, node*> splitSize(int k){
    if(k == (L?L->cnt:0)){
      auto x = L; L = 0; up();
      return {x, this};
    }
    else if(k < (L?L->cnt:0)){
      //if(!L)return{nullptr, this};
      auto p = L->splitSize(k);
      assert(p.ff->cnt == k);
      L = p.ss; up();
      return {p.ff, this};
    }else{
      if(!R)return{this, nullptr};
      auto p = R->splitSize(k-1-(L?L->cnt:0));
      R = p.ff; up();
      assert(cnt == k);
      return {this, p.ss};
    }
  }
  friend node* merge(node* a, node* b){
    if(!a)return b;
    if(!b)return a;
    if(a->key < b->key)
      return a->R = merge(a->R, b), a->up(), a;
    else
      return b->L = merge(a, b->L), b->up(), b;
  }
} *root = 0;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    srand(time(0));
    lld ans = 0;
    for(int i = 0; i < min(n, d); i++){
      if(!root)root = new node(attraction[i]);
      else{
        auto p = root->splitVal(attraction[i]);
        root = merge(merge(p.ff, new node(attraction[i])), p.ss);
      }
      auto p = root->splitSize(d-i);
      assert(p.ff->cnt == min(i+1, d-i));
      //cout << d-i << " " << p.ff->sum << endl;
      ans = max(ans, p.ff->sum);
      root = merge(p.ff, p.ss);
    }
    return ans;
}

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