裏紙

ほぼ競プロ、たまに日記

CF 596C - Wilbur and Points

・問題
http://codeforces.com/problemset/problem/596/C

・概要
xy直交座標平面上に点がn個ある。x座標、y座標は共に0以上。
n個の点に、1~nの名前を付けたい。ただし条件がある:
 1.点(x,y)にiの名前をつけるとき、(x<=x' && y<=y')を満たす点(x',y')はi以下の名前を持ってはならない。
要するに、1~nの名前をもつ点(x,y)を順に置いていく時に、(0,0)と(x,y)の内側を領域にする長方形(とか直線)をイメージして、それを重ねていくときに必ず新しい領域が生まれるということ。(紙に書くとそういうイメージだった)
 2.各点は、y-xという評価値を持つ。iの名前を持つ点は、yi-xi=wiでなければならない。

これらの条件を満たす名前の割り当て方があればYESと答え点の組合せを1から順に出力、
なければNOと答えよ。

  • n<=100000
  • 0<=x,y<=100000
  • -100000<=w<=1000000

・アイデア
最初、サンプルケースを図に起こしてみる。これって、y=-xの直線で切りながらやっていけばいいんじゃね?(つまりx+yの値を取って小さい順でソート)とか思うが、極端にx座標が大きい例とか考えるとだめだなあってすぐボツ。

座標を書いて、まっさらな状態から1個目の点を置くと、それに準じた領域が出来る(斜線でそめてみる)。次の点を置く時に、この領域内に点をおくことは許されないので、まだ白い部分に次の点を置く必要がある。次の点を置く。長方形を2個重ねたような領域ができる。

問題はテストケースのように置く順序がどっちでも許されるってことだなあ...とここで2番目の条件に注目してみる。
すると、i番目に置くべき点は一意に決まるのではってなる。yi-xi=wiでなければならないということは、i番目の点は直線y=x+w上の点であるということになる。そして、もしサンプルケースのようにwの値が同じものが複数出てきた場合は、まだ使用していないこの直線上の点でx座標が最も小さい点を選ばなければならない(条件1に反しないようにするため)。

置く一意に決まるならO(n)で点を置いていけるじゃないか!となるが、ここでそのような順序で置こうとした時にi番目の点が既に上で言うところの斜線部に入っていてしまうと答えはNOになるな、と考え、点1回設置する毎に領域に含まれる判定と領域の更新とを行う必要があるとなる。
x座標ごとにy座標のどこまでが領域に含まれるかを配列で持って更新しよう、と思ったら「あれ、これ1回の操作にO(n)かかって合計O(n^2)だし絶対間に合わない」ってなる。
そして、図を見てると領域が必ず階段状になってることに気づく。そうすると、ある点から見た時、この点のy座標で領域に含まれているのはそれより右側のy座標の最大値だってなる。つまり区間[x,100000]の配列の最大値
...あれ、これこそsegtreeを使うのではないか...?(その日CODE FESTIVALでその話をした顔)
そうすれば区間の更新もそのx座標に対してのy座標を更新するだけで済む!(それより右側は0になったままでもsegtreeで最大値持ってくれば正しく領域判定できる)

1回も書いたことないので、理屈があんまりわかってなかったまま蟻本を開き、見よう見真似でsegtreeを書き始める
(この辺でコンテストが終了し、この30分後にACして悲しむことになる)
これで領域判定・更新がO(logn)なので全体としてO(nlogn)だ〜 → segtreeのサイズが小さすぎて1回バグったが、サイズをよくわからないけど適当に大きめに直してAC

感想としては、意外とsegtreeは書くべき量が少なかった。これはこの手の問題では確かに絶大な効果を発揮できるって思った。ちゃんとsegtreeのページ読んで、本戦Dもsegtreeで実装してみます。
コンテスト時間内に間に合いたかった...

・実装(C++)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;

const long N = 1000001;

long s;
long dat[2*N-1];

void init(int n_){
  s=1;
  while(s<n_) s*=2;

  for(long i=0; i<2*s-1; ++i) dat[i] = -1;
}

void update(long k, long a){
  k+=s-1;
  dat[k]=a;
  while(k>0){
    k = (k-1)/2;
    dat[k] = max(dat[k*2+1],dat[k*2+2]);
  }
}

long query(long a, long b, long k, long l, long r){
  if(r<=a || b<=l) return -1;

  if(a<=l && r<=b) return dat[k];
  else{
    long vl = query(a,b,k*2+1,l,(l+r)/2);
    long vr = query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
}

queue< pair<long,long> > q[200001]; //y座標-x座標+100000


int main(){
  long n;
  cin >> n;

  init(n);

  vector< pair<long,long> > p(n);
  for(long i=0; i<n; ++i) scanf(" %ld %ld", &p[i].first, &p[i].second);
  sort(p.begin(),p.end());

  for(long i=0; i<n; ++i){
    //printf(" focus %ld, %ld\n", p[i].first, p[i].second);
    q[p[i].second-p[i].first+100000].push(p[i]);
  }

  vector< pair<long,long> > ans;
  ans.resize(n);

  bool valid=true;
  for(long i=0; i<n; ++i){
    long w;
    scanf(" %ld", &w);

    if(valid){
      if(q[w+100000].size()==0){
        valid=false;
      }
      else{ //要素が見つかった
        pair<long,long> tmp = q[w+100000].front();
        //printf("%ld, %ld\n", tmp.first, tmp.second);
        q[w+100000].pop();

        long lim = query(tmp.first,100001,0,0,s);
        //printf("lim=%ld\n", lim);
        if(lim<tmp.second){ //大丈夫
          update(tmp.first,tmp.second);
          ans[i].first = tmp.first;
          ans[i].second = tmp.second;
        }
        else valid=false;
      }
    }
  }

  if(valid){
    printf("YES\n");
    for(long i=0; i<n; ++i) printf("%ld %ld\n",ans[i].first, ans[i].second);
  }
  else printf("NO\n");
}