제출 #1038025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038025		Mr_Husanboy	모임들 (IOI18_meetings)	C++17	19 / 100	5532 ms	15956 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){
  return a.size();
}
const ll infl = 1e18 + 110;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());




struct SegmentTree{

    //To change
    struct Node{
        //defaults
        ll mn = 0, add = 0; bool marked = false;
        void apply(ll val){
            mn += val;
            add += val;
            marked = true;
        }
    };

    void push(int x){
        if(t[x].marked){
            t[x << 1].apply(t[x].add);
            t[x << 1 | 1].apply(t[x].add);
            t[x].add = 0; t[x].marked = false;
        }
    }

    Node merge(Node a, Node b){
        Node res;
        if(a.mn < b.mn){
            res.mn = a.mn;
        }else{
            res.mn = b.mn;
        }
        return res;
    }
    Node neutral;
    vector<Node> t;
    int n;

    //construction

    void init(int _n){
        n = _n;
        t.assign(4 * n, neutral);
    }

    void build(vector<int> &a, int x, int lx, int rx){
        if(lx == rx){
            t[x].mn = a[lx];
            return;
        }
        int mx = (lx + rx) >> 1;
        build(a, x << 1, lx, mx);
        build(a, x << 1 | 1, mx + 1, rx);
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    void upd(int x, int lx, int rx, int l, int r, int val){
        if(rx < l || r < lx) return;
        if(l <= lx && rx <= r){
            t[x].apply(val); return;
        }
        push(x);
        int mx = (lx + rx) >> 1;
        upd(x << 1, lx, mx, l, r, val);
        upd(x << 1 | 1, mx + 1, rx, l, r, val);
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    Node get(int x, int lx, int rx, int l, int r){
        if(rx < l || r < lx){
            return neutral;
        }
        if(l <= lx && rx <= r){
            return t[x];
        }
        push(x);
        int mx = (lx + rx) >> 1;
        return merge(get(x << 1, lx, mx, l, r), get(x << 1 | 1, mx + 1, rx, l, r));
    }

    // lessen

    void build(vector<int> &a){
        int sz = len(a);
        init(sz);
        build(a, 1, 0, n - 1);
    }

    void upd(int l, int r, int val){
        upd(1, 0, n - 1, l, r, val);
    }

    Node get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }
    ll mn(){
      return t[1].mn;
    }
};

vector<long long> minimum_costs(vector<int> h, vector<int> L,
                                     vector<int> R) {
  int n = len(h);
  int q = len(L);
  vector<ll> res(q, infl);
  vector<int> lef(n), rig(n);
  vector<int> st;
  for(int i = 0; i < n; i ++){
    while(!st.empty() && h[st.back()] <= h[i]){
      st.pop_back();
    }
    if(st.empty()) lef[i] = -1;
    else lef[i] = st.back();
    st.push_back(i);
  }
  st.clear();
  for(int i = n - 1; i >= 0; i --){
    while(!st.empty() && h[st.back()] <= h[i]){
      st.pop_back();
    }
    if(st.empty()) rig[i] = n;
    else rig[i] = st.back();
    st.push_back(i);
  }

  SegmentTree t;
  t.init(n);



  vector<int> ind(q);
  iota(all(ind), 0);
  int block = sqrt(n);
  sort(all(ind), [&](int i, int j){
    if((L[i] + 1) / block == (L[j] + 1) / block){
      if(R[i] == R[j]) return L[i] < L[j];
      return R[i] < R[j];
    }
    return (L[i] + 1) / block < (L[j] + 1) / block;
  });
  int curl = 0, curr = -1;

  auto del = [&](int i){
    int l = lef[i], r = rig[i];
    t.upd(l + 1, r - 1, -h[i]);
    while(l >= 0){
      t.upd(lef[l] + 1, l, -h[l]);
      l = lef[l];
    }
    while(r < n){
      t.upd(r, rig[r] - 1, -h[r]);
      r = rig[r];
    }
  };
  auto add = [&](int i){
    int l = lef[i], r = rig[i];
    //cout << i << ' ' << l << ' ' <<  r << endl;
    t.upd(l + 1, r - 1, h[i]);
    while(l >= 0){
      t.upd(lef[l] + 1, l, h[l]);
      l = lef[l];
    }
    while(r < n){
      t.upd(r, rig[r] - 1, h[r]);
      r = rig[r];
    }
  };


  auto make = [&](int l, int r)->void{
    while(curl < l){
      del(curl);
      curl ++;
    } 
    while(curl > l){
      curl --;
      add(curl);
    }
    while(curr < r){
      //cout << curr << endl;
      curr ++;
      add(curr);
    }
    while(curr > r){
      del(curr);
      curr --;
    }
  };
  for(auto u : ind){
    //cout << L[u] << ' ' << R[u] << endl;
    make(L[u], R[u]);
    res[u] = t.mn();
  }
  return res;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40