제출 #1316520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316520		ghos007	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	1936 ms	705624 KiB

Main

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e17;
struct node {
  int maxx_val = -INF;
  node *left ;
  node *right;
  node() {
    maxx_val = -INF;
    left = 0;
    right = 0;
  }
  node * go_to_l() {
    if (!left) left = new node();
    return left;
  }
  node * go_to_r() {
    if (!right) right = new node();
    return right;
  }
};
void upd(node *u,int l,int r,int val,int pos) {
  if (r - l == 1) {
    u->maxx_val = max(val,u->maxx_val);
    return;
  }
  int mid = (l + r) / 2;
  if (pos < mid) {
    upd(u->go_to_l(),l,mid,val,pos);
  }else {
    upd(u->go_to_r(),mid,r,val,pos);
  }
  u->maxx_val = max(u->go_to_l()->maxx_val,u->go_to_r()->maxx_val);
}
int get(node *u,int l,int r,int ql,int qr) {
  if (r <= ql || l >= qr) return -INF;
  if (l >= ql && r <= qr) return u->maxx_val;
  int mid = (l + r) / 2;
  return max(get(u->go_to_l(),l,mid,ql,qr),get(u->go_to_r(),mid,r,ql,qr));
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector <pair<int,int>> vec(n);
  for (int i = 0;i < n;i++) {
    cin >> vec[i].second >> vec[i].first;
  }
  sort(vec.begin(), vec.end());
  int ans = 0;
  node* root1 = new node();
  node* root2 = new node();
  int L = 0;
  int R = 1e10;
  for (int i = n - 1;i >= 0;i--) {
    int v1 = vec[i].first + vec[i].second;
    int v2 = vec[i].first - vec[i].second;
    int var1 = get(root1,L,R,0,vec[i].second);
    int var2 = get(root2,L,R,vec[i].second,R);
    if (v1 > var1 && v2 > var2) {
      ans++;
    }
    upd(root1,L,R,v1,vec[i].second);
    upd(root2,L,R,v2,vec[i].second);
  }
  cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31