제출 #763035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763035		ind1v	Just Long Neckties (JOI20_ho_t1)	C++11	100 / 100	195 ms	21568 KiB

ho_t1

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200005;
 
struct segment_tree {
  int mx[4 * N];
  
  segment_tree() {
    memset(mx, -0x3f, sizeof(mx));
  }
  
  void upd(int id, int tl, int tr, int pos, int val) {
    if (tl == tr) {
      mx[id] = val;
      return;
    }
    int tm = tl + tr >> 1;
    if (pos <= tm) {
      upd(id << 1, tl, tm, pos, val); 
    } else if (tm + 1 <= pos) {
      upd(id << 1 | 1, tm + 1, tr, pos, val);
    }
    mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  }
};
 
int n;
int a[N], b[N];
int c[N], ans[N];
segment_tree st;
set<pair<int, int>> s;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n + 1; i++) {
    cin >> a[i];
    c[i] = a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  sort(b + 1, b + n + 1);
  sort(a + 1, a + n + 2);
  for (int i = 1; i <= n + 1; i++) {
    s.insert({a[i], i});
  }
  for (int i = 1; i <= n; i++) {
    st.upd(1, 1, n, i, a[i + 1] - b[i]);
  }
  ans[1] = max(0, st.mx[1]);
  for (int i = 2; i <= n + 1; i++) {
    st.upd(1, 1, n, i - 1, a[i - 1] - b[i - 1]);
    ans[i] = max(0, st.mx[1]);
  }
  for (int i = 1; i <= n + 1; i++) {
    auto it = s.lower_bound({c[i], -1});
    cout << ans[it->second] << ' ';
    s.erase(it);
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t1.cpp: In member function 'void segment_tree::upd(int, int, int, int, int)':
ho_t1.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91