Submission #1154015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154015		YSH2020	Sjekira (COCI20_sjekira)	C++20	10 / 110	74 ms	26440 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
  int l, r, m, val = 0, pos = 0;
  node *lf = nullptr; node *rg = nullptr;
  node (int _l, int _r): l(_l), r(_r), m((_l+_r)/2) {}
  pair<int,int> qry(int x, int y) {
    if (r < x || l > y) return {0,0};
    if (x <= l && r <= y) return {val, pos};
    if (!lf) create();
    auto tmp1 = lf->qry(x, y);
    auto tmp2 = rg->qry(x, y);
    if (tmp1.first >= tmp2.first) return tmp1;
    else return tmp2;
  }
  void upd(int p, int v) {
    if (l == r) {val = v; pos = l;return;}
    if (!lf) create();
    if (p <= m) lf->upd(p, v);
    else rg->upd(p, v);
    if (lf->val >= rg->val) {pos = lf->pos; val = lf->val;}
    else {pos = rg->pos; val  = rg->val;}
  }
  void create() {
    if (l != r) {
      lf = new node(l, m);
      rg = new node(m+1, r);
    }
  }
}*root;

//build cartesian tree because i have to :(

vector<vector<int>> adj(100005);
int cost[100005];
void build(int s, int e, int p) {
  if (e < s) return;
  int x = root->qry(s, e).second;
  if (p != -1) adj[p].push_back(x);
  build(s, x-1, x);
  build(x+1, e, x);
}
int ans;
void dfs(int n, int p) {
  for (auto i:adj[n]) {
    dfs(i, n);
    ans += cost[i]+cost[n];
  }
}

signed main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> cost[i];
  root = new node(0, n);
  for (int i= 0; i < n; i++) root->upd(i, cost[i]);
  build(0, n-1, -1);
  ans = 0;
  dfs(root->qry(0, n-1).second, -1);
  cout << ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60