oj.uz

Submission #102840

# Submission time Handle Problem Language Result Execution time Memory
102840 2019-03-28T00:54:48 Z wxh010910 Holiday (IOI14_holiday) C++17
100 / 100
 1359 ms 9340 KB 
#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;

class node {
 public:
  node* p;
  node* l;
  node* r;
  int sz;
  int key;
  int self;
  long long sum;

  node(int key, int self): key(key), self(self) {
    p = l = r = NULL;
    sum = self;
    sz = 1;
  }

  void pull() {
    sz = 1;
    sum = self;
    if (l != NULL) {
      l->p = this;
      sz += l->sz;
      sum += l->sum;
    }
    if (r != NULL) {
      r->p = this;
      sz += r->sz;
      sum += r->sum;
    }
  }
};

bool is_bst_root(node* v) {
  if (v == NULL) {
    return false;
  }
  return (v->p == NULL || (v->p->l != v && v->p->r != v));
}

void rotate(node* v) {
  node* u = v->p;
  v->p = u->p;
  if (v->p != NULL) {
    if (v->p->l == u) {
      v->p->l = v;
    }
    if (v->p->r == u) {
      v->p->r = v;
    }
  }
  if (v == u->l) {
    u->l = v->r;
    v->r = u;
  } else {
    u->r = v->l;
    v->l = u;
  }
  u->pull();
  v->pull();
}

void splay(node* v) {
  if (v == NULL) {
    return;
  }
  while (!is_bst_root(v)) {
    node* u = v->p;
    if (!is_bst_root(u)) {
      if ((u->l == v) ^ (u->p->l == u)) {
        rotate(v);
      } else {
        rotate(u);
      }
    }
    rotate(v);
  }
}

node* insert(node* v, node* u) {
  u->l = u->r = NULL;
  while (true) {
    ++v->sz;
    v->sum += u->self;
    if (u->key > v->key) {
      if (v->r == NULL) {
        v->r = u;
        u->p = v;
        splay(u);
        return u;
      } else {
        v = v->r;
      }
    } else {
      if (v->l == NULL) {
        v->l = u;
        u->p = v;
        splay(u);
        return u;
      } else {
        v = v->l;
      }
    }
  }
}

node* get_rightmost(node* v) {
  while (v->r != NULL) {
    v = v->r;
  }
  splay(v);
  return v;
}

node* erase(node* v, int key) {
  while (true) {
    if (v->key == key) {
      break;
    } else if (key > v->key) {
      v = v->r;
    } else {
      v = v->l;
    }
  }
  splay(v);
  node* l = v->l;
  node* r = v->r;
  v->l = v->r = NULL;
  if (l != NULL) {
    l->p = NULL;
  }
  if (r != NULL) {
    r->p = NULL;
  }
  if (l == NULL) {
    return r;
  }
  if (r == NULL) {
    return l;
  }
  l = get_rightmost(l);
  l->r = r;
  l->pull();
  return l;
}

long long query(node* &v, int k) {
  long long ans = 0;
  while (true) {
    if (v->r != NULL) {
      if (v->r->sz >= k) {
        v = v->r;
        continue;
      } else {
        k -= v->r->sz;
        ans += v->r->sum;
      }
    }
    ans += v->self;
    if (!--k) {
      splay(v);
      return ans;
    }
    v = v->l;
  }
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  vector<int> order(n);
  for (int i = 0; i < n; ++i) {
    order[i] = i;
  }
  sort(order.begin(), order.end(), [&](int a, int b) {
    return attraction[a] < attraction[b];
  });
  vector<int> pos_in_order(n);
  for (int i = 0; i < n; ++i) {
    pos_in_order[order[i]] = i;
  }
  vector<node*> tree(n);
  for (int i = 0; i < n; ++i) {
    tree[i] = new node(pos_in_order[i], attraction[i]);
  }
  node* root = tree[start];
  int pl = start, pr = start;
  long long ans = 0;
  auto extend = [&](int l, int r) {
    while (pr < r) {
      root = insert(root, tree[++pr]);
    }
    while (pl > l) {
      root = insert(root, tree[--pl]);
    }
    while (pr > r) {
      root = erase(root, pos_in_order[pr--]);
    }
    while (pl < l) {
      root = erase(root, pos_in_order[pl++]);
    }
  };
  function<void(int, int, int, int)> solve = [&](int l, int r, int ll, int rr) {
    if (l > r) {
      return;
    }
    int mid = (l + r) >> 1, pos = -1;
    long long best = -1;
    for (int i = ll; i <= rr; ++i) {
      int cnt = d - (i - mid) - min(i - start, start - mid);
      if (cnt <= 0) {
        break;
      }
      extend(mid, i);
      long long value = root->sz <= cnt ? root->sum : query(root, cnt);
      if (best < value) {
        best = value;
        pos = i;
      }
    }
    ans = max(ans, best);
    solve(l, mid - 1, ll, pos);
    solve(mid + 1, r, pos, rr);
  };
  solve(max(0, start - d + 1), start, start, min(n - 1, start + d - 1));
  return ans;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8576 KB Output is correct
2 Correct 27 ms 8568 KB Output is correct
3 Correct 37 ms 8508 KB Output is correct
4 Correct 27 ms 8576 KB Output is correct
5 Correct 128 ms 7920 KB Output is correct
6 Correct 24 ms 2688 KB Output is correct
7 Correct 59 ms 4620 KB Output is correct
8 Correct 71 ms 5376 KB Output is correct
9 Correct 19 ms 2048 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 11 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8576 KB Output is correct
2 Correct 31 ms 8568 KB Output is correct
3 Correct 170 ms 4072 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 1359 ms 9340 KB Output is correct
9 Correct 1220 ms 9336 KB Output is correct