Submission #172429

#	Time	Username	Problem	Language	Result	Execution time	Memory
172429		AlexLuchianov	Holiday (IOI14_holiday)	C++14	100 / 100	2070 ms	13608 KiB

holiday

#include "holiday.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;

std::unordered_map<int,int> code, decode;
void normalize(int n, int attraction[]){
  std::vector<int> temp;
  for(int i = 0; i < n; i++)
    temp.push_back(attraction[i]);
  std::sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++) {
    code[temp[i]] = 1 + i;
    decode[1 + i] = temp[i];
  }
}
class FenwickTree{
private:
  int n;
  std::vector<ll> aib;
public:
  FenwickTree(int n = 0){
    this->n = n;
    aib.resize(n + 1, 0);
  }
  void update(int x, int val){
    if(x == 0)
      return ;
    while(x <= n){
      aib[x] += val;
      x += x ^ (x & (x - 1));
    }
  }
  ll query(int x){
    ll result = 0;
    while(0 < x){
      result += aib[x];
      x = x & (x - 1);
    }
    return result;
  }

  ///find first position with target <= query(pos)
  ///if it does not exist, return n + 1
  int lowerthan(ll target){
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2){
      if(x + jump <= n && aib[x + jump] < target){
        x += jump;
        target -= aib[x];
      }
    }
    return x + 1;
  }
};

namespace Magicstruct{
  int n;
  FenwickTree app, sum;
  void initialize(int n_){
    n = n_;
    app = FenwickTree(n);
    sum = FenwickTree(n);
  }
  void insert(int val){
    assert(0 < code[val]);
    int pos = code[val];
    app.update(pos, 1);
    sum.update(pos, val);
    //std::cout << "insert " << pos << " " << val << '\n';
  }
  void erase(int val){
    assert(0 < code[val]);
    int pos = code[val];
    app.update(pos, -1);
    sum.update(pos, -val);
  }
  ///returns sum of the k biggest elements
  ll query(int k){
    int totalsz = app.query(n);
    if(k <= 0)
      return 0;
    else if(totalsz <= k)
      return sum.query(n);
    else {
      int pos = app.lowerthan(totalsz - k + 1);
      //std::cout << "Query: " << pos << " " << totalsz << " " << app.query(pos - 1) << " " <<  k << " " << decode[pos] << '\n';
      ll result = sum.query(n) - sum.query(pos - 1) - (totalsz - app.query(pos - 1) - k) * decode[pos];
      return result;
    }
  }
}

ll v[1 + nmax], sol[1 + nmax], dp[1 + nmax];
int n, start, d;

void addinterval(int x, int y){
  for(int i = x;i <= y; i++) {
    Magicstruct::insert(v[i]);
  }
}
void deleteinterval(int x, int y){
  for(int i = x;i <= y; i++)
    Magicstruct::erase(v[i]);
}

void eval(int pos, int solx, int soly){
  dp[pos] = 0;
  sol[pos] = solx;
  for(int i = solx; i <= soly; i++){
    Magicstruct::insert(v[i]);
    ll result = Magicstruct::query(d - (i + start - 2 * pos));
    //std::cout << "|" << pos << " " << i << " " << result << " " << d - (i + start - 2 * pos) << " " << Magicstruct::app.query(n) <<  '\n';
    if(dp[pos] < result){
      dp[pos] = result;
      sol[pos] = i;
    }
  }
  deleteinterval(solx, soly);
}

void divide(int from, int to, int solx, int soly){
  if(from <= to && solx <= soly){
    int mid = (from + to) / 2;
    addinterval(mid, to);
    eval(mid, solx, soly);
    deleteinterval(mid, to);

    addinterval(mid, to);
    divide(from, mid - 1, solx, sol[mid]);
    deleteinterval(mid, to);

    addinterval(solx, sol[mid] - 1);
    divide(mid + 1, to, sol[mid], soly);
    deleteinterval(solx, sol[mid] - 1);
  }
}

ll solve(){
  Magicstruct::initialize(n);
  for(int i = 0; i < n; i++)
    dp[i] = sol[i] = 0;
  eval(start, start, n - 1);

  Magicstruct::insert(v[start]);
  divide(0, start - 1, start + 1, n - 1);
  Magicstruct::erase(v[start]);

  ll result = 0;
  for(int i = 0; i < n; i++)
    result = MAX(result, dp[i]);
  return result;
}

long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
  n = n_;
  start = start_;
  d = d_;
  normalize(n, attraction);
  for(int i = 0; i < n; i++)
    v[i] = attraction[i];

  ll result1 = 0, result2 = 0;
  result1 = solve();
  //*
  start = n - 1 - start;
  for(int i = 0; i < n; i++)
    if(i <= n - 1 - i)
      std::swap(v[i], v[n - 1 - i]);
  result2 = solve();
  //*/
  return MAX(result1, result2);
}

Compilation message (stderr)

holiday.cpp: In function 'void normalize(int, int*)':
holiday.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++) {
                  ~~^~~~~~~~~~~~~

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