[伯俊]データカー#22942

説明:
質問条件ではNが最大20万となっているため,O(N^2)問を解くことができない.
考えましたが、解題方法が思いつかないので、他の人の解題方法を参考にしてスタック構造で解題すればいいです.
x軸に接する円座標を基準に、左かっこの右かっこのopenをかっこのcloseと見なし、stackに入れて比較すればよい.
本人は入力中に{ x축에 닿는 좌표, open/close, 원의번호 }として保存し、x軸に接触する座標に基づいて一度ソートし、スタックに入れるとcloseがポップアップし、ペアが正しい場合は続行し、エラーであれば「NO」を出力する.
最後に、スタックが空であるかどうかを確認し、結果を返します.
Node.説明する

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const points = input.slice(1).map((v) => v.split(' ').map(Number));

const solution = (N, points) => {
  const arr = [];
  points.forEach(([x, r], i) => {
    arr.push([x - r, 'open', i]);
    arr.push([x + r, 'close', i]);
  });
  arr.sort((a, b) => a[0] - b[0]);
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    const [, state, id] = arr[i];
    if (state === 'open') {
      stack.push(id);
    } else {
      const top = stack[stack.length - 1];
      if (top === id) stack.pop();
      else return 'NO';
    }
  }
  if (stack.length !== 0) return 'NO';
  return 'YES';
};

console.log(solution(N, points));

C++プール

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    string state;
    int id;
};

bool compare(Point& a, Point& b) {
    return a.x < b.x;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<Point> V;
    int N; cin >> N;
    for (int i=0; i<N; i++) {
        int x, r;
        cin >> x >> r;
        V.push_back({ x-r, "open", i });
        V.push_back({ x+r, "close", i });
    }
    
    sort(V.begin(), V.end(), compare);
    stack<int> S;
    for(auto point : V) {
        if (point.state == "open") S.push(point.id);
        else {
            if (S.top() != point.id) {
                cout << "NO" << '\n';
                return 0;
            } else {
                S.pop();
            }
        }
    }
    if (!S.empty()) cout << "NO" << '\n';
    else cout << "YES" << '\n';
    return 0;
}