제출 #1197389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197389		mychecksedad	Road Construction (JOI21_road_construction)	C++20	100 / 100	2802 ms	955116 KiB

road_construction

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;

pair<ll, int> f(pair<ll, int> x, pair<ll, int> y){
  if(x.ff < y.ff) return x;
  if(y.ff < x.ff) return y;
  return (x.ss < y.ss) ? x : y;
}

struct Node{
  Node *L, *R;
  pair<ll, int> mn = {INF, -1};
  int idx;
  Node(){
    L=R=nullptr;
    idx = -1;
  }
  Node(Node *l, Node *r){
    L = l, R = r;
    mn = f((L ? L->mn : mn), (R ? R->mn : mn));
  }
  Node(ll val, int idx){
    mn = {val, idx};
  }
};

Node *build(int l, int r){
  if(l == r){
    return new Node();
  }
  int m = l+r>>1;
  return new Node(build(l, m), build(m+1, r));
}

Node* upd(Node *v, int l, int r, int p, ll val){
  if(l == r){
    if(val == -INF){
      return new Node();
    }
    return new Node(val, l);
  }
  int m = l+r>>1;
  if(p <= m){
    return new Node(upd(v->L, l, m, p, val), v->R);
  }
  return new Node(v->L, upd(v->R, m+1, r, p, val));
}

pair<ll, int> get(Node *v, int l, int r, int ql, int qr){
  if(l > qr || ql > r) return pair<ll, int>{INF, -1};
  if(ql <= l && r <= qr){
    return v->mn;
  }
  int m = l+r>>1;
  return f(
    get(v->L, l, m, ql, qr),
    get(v->R, m+1, r, ql, qr)
  );
}

int n, k;
array<int, 3> a[N], b[N];
void solve(){
  cin >> n >> k;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0] >> a[i][1];
    a[i][2] = i;
  }
  for(int i = 1; i <= n; ++i){
    b[i][0] = a[i][1];
    b[i][1] = a[i][0];
    b[i][2] = i;
  }
  sort(b+1, b+1+n); // y positions
  for(int i = 1; i <= n; ++i) a[b[i][2]][2] = i;
  sort(a+1, a+1+n);
  vector<Node*> T1, T2;
  T1.pb(build(1, n));
  T2.pb(build(1, n));
  
  // for(int i = 1; i <= n; ++i){
  //   cout << a[i][0] << ' ' << a[i][1] << ' ' << a[i][2] << '\n';
  // }

  priority_queue<array<ll, 3>> Q;

  for(int i = 1; i <= n; ++i){
    auto L = get(T1.back(), 1, n, 1, a[i][2] - 1);
    auto R = get(T2.back(), 1, n, a[i][2] + 1, n);
    L.ff += a[i][0] + a[i][1];
    R.ff += a[i][0] - a[i][1];
    auto res = f(L, R);
    if(res.ss != -1){
      Q.push({-res.ff, i, res.ss});
    }
    // cout << L.ff << ' ' << L.ss << '\n';
    T1.pb(upd(T1.back(), 1, n, a[i][2], -a[i][1]-a[i][0]));
    T2.pb(upd(T2.back(), 1, n, a[i][2], a[i][1]-a[i][0]));
  }

  while(k--){
    auto [val, v, idx] = Q.top(); Q.pop();
    // cout << v << ' ' << idx << ' ';
    cout << -val << '\n';
    T1[v - 1] = upd(T1[v - 1], 1, n, idx, -INF);
    T2[v - 1] = upd(T2[v - 1], 1, n, idx, -INF);
    auto L = get(T1[v - 1], 1, n, 1, a[v][2] - 1);
    auto R = get(T2[v - 1], 1, n, a[v][2] + 1, n);
    L.ff += a[v][0] + a[v][1];
    R.ff += a[v][0] - a[v][1];
    auto res = f(L, R);
    if(res.ss != -1){
      Q.push({-res.ff, v, res.ss});
    }
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35