제출 #1189993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189993		SalihSahin	나일강 (IOI24_nile)	C++20	100 / 100	327 ms	52160 KiB

nile

#include "bits/stdc++.h"
#include "nile.h"
#define pb push_back
using namespace std;
#define ll long long

const ll inf = 1e16;
const int N = 1e5 + 5;

vector<ll> GA(N), GB(N);

struct node{
  int l, r;
  ll dp[3][3]; // sol sag skip
  int go[2][2]; // go[i. adamdan][j + 1 uzunlugunda sola]

  node(){
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        dp[i][j] = inf;
      }
    }

    for(int i = 0; i < 2; i++){
      for(int j = 0; j < 2; j++){
        go[i][j] = 0;
      }
    }
    
    l = 0, r = 0;
  }
};

node merge(node &a, node &b){
  node res = node();

  for(int l = 0; l < 3; l++){
    for(int r = 0; r < 3; r++){
       if(l + r > (a.r - a.l + 1) + (b.r - b.l + 1)) continue;
       if(l + r == (a.r - a.l + 1) + (b.r - b.l + 1)){
          res.dp[l][r] = 0;
          continue;
       }

       if(r >= (b.r - b.l + 1)){
         res.dp[l][r] = min(res.dp[l][r], a.dp[l][r - (b.r - b.l + 1)]);
         continue;
       }
       if(l >= (a.r - a.l + 1)){
         res.dp[l][r] = min(res.dp[l][r], b.dp[l - (a.r - a.l + 1)][r]);
         continue;
       }

       res.dp[l][r] = min(res.dp[l][r], a.dp[l][0] + b.dp[0][r]);
       if(b.go[0][0]) res.dp[l][r] = min(res.dp[l][r], a.dp[l][1] + (GB[a.r] + GB[b.l]) + b.dp[1][r]);
       if(b.go[0][1] && a.l < a.r) res.dp[l][r] = min(res.dp[l][r], a.dp[l][2] + (GB[a.r-1] + GA[a.r] + GB[b.l]) + b.dp[1][r]);
       if(b.go[1][1]) res.dp[l][r] = min(res.dp[l][r], a.dp[l][1] + (GB[a.r] + GA[b.l] + GB[b.l+1]) + b.dp[2][r]);
    }
  }

  res.l = a.l;
  res.r = b.r;

  res.go[0][0] = a.go[0][0];
  res.go[0][1] = a.go[0][1];
  if(a.l < a.r){
    res.go[1][0] = a.go[1][0];
    res.go[1][1] = a.go[1][1];
  }
  else{
    res.go[1][0] = b.go[0][0];
    res.go[1][1] = b.go[0][1];
  }

  return res;
}

struct SEGT{
  vector<node> tree;

  void init(int n){
    tree.assign(4*n, node());
  }

  void build(int ind, int l, int r){
     if(l == r){
        tree[ind].l = l;
        tree[ind].r = r;
        tree[ind].dp[0][0] = GA[l];
        tree[ind].dp[1][0] = tree[ind].dp[0][1] = 0;
     }
     else{
        int m = (l + r)/2;
        build(ind*2, l, m);
        build(ind*2+1, m+1, r);
        tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
     }
  }

  void update(int ind, int l, int r, int pos, int posi){
    if(l == r){
      tree[ind].go[0][posi] = 1;
    }
    else{
        int m = (l + r)/2;
        if(pos <= m) update(ind*2, l, m, pos, posi);
        else update(ind*2+1, m+1, r, pos, posi);
        tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
    }
  }
};

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  int n = W.size();
  vector<array<ll, 3> > art(n);
  for(int i = 0; i < n; i++){
    art[i] = {W[i], A[i], B[i]};
  }
  sort(art.begin(), art.end());
  for(int i = 1; i <= n; i++){
    GA[i] = art[i-1][1];
    GB[i] = art[i-1][2];
  }

  int q = E.size();
  vector<ll> ans(q);
  vector<pair<ll, ll> > query(q);
  for(int i = 0; i < q; i++){
    query[i] = {E[i], i};
  }
  sort(query.begin(), query.end());
  vector<array<ll, 3> > upd;
  for(int i = 0; i < n; i++){
    if(i > 0) upd.pb({art[i][0] - art[i-1][0], i+1, 0});
    if(i > 1) upd.pb({art[i][0] - art[i-2][0], i+1, 1});
  }
  sort(upd.begin(), upd.end());
  int updind = 0;

  SEGT seg;
  seg.init(n);
  seg.build(1, 1, n);

  for(int qt = 0; qt < q; qt++){
      ll d = query[qt].first;
      while(updind < upd.size() && upd[updind][0] <= d){
        seg.update(1, 1, n, upd[updind][1], upd[updind][2]);
        updind++;
      }
      ans[query[qt].second] = seg.tree[1].dp[0][0];
  }

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18