AtCoder K2PC Hard B 虫歯

http://k2pc-hard.contest.atcoder.jp/tasks/k2pc001_h2

問題

深さK(1<=K<=50)の完全二分木がある(深さ1なら3つのノードがあることに注意)。
深さがiで左からj番目のノードのことを(i, j)と表し、それがN(0<=N<=10^5)つ与えられる。
この時、この木のノードのうち、与えられた座標のうちどれも通らないでルートノードにたどり着けるノードの数を数えろ。

回答

各深さに対して、今の高さより上のものを見て駄目になる区間を求め、それらの共通部分をその高さのノード数から引いて、それらを足す。
共通部分を求めるのにはhttp://d.hatena.ne.jp/anta1/20120815/1345026885のものを使った。
O(K N log N)

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#ifdef _MSC_VER
#define aut(v, x) auto v = x
#else
#define aut(v, x) __typeof(x) v = (x)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
 
int main() {
	int k, n;
	vector<pair<ll,ll> > p;
	scanf("%d%d",&k,&n); k ++;
	rep(i,n){ll y, x; scanf("%lld%lld",&y,&x),p.pb(mp(y,x-1));};
	sort(all(p));
	ll r = 0;
	for(int yy = k-1; yy >= 0; -- yy) {
		aut(j, p.begin());
		vector<pair<ll,ll> > d;
		rep(y, k) {
			for(; j != p.end() && j->first == y; ++ j) {
				if(y <= yy) {
					d.pb(mp(j->second << (yy - y), ((j->second+1) << (yy - y)) - 1));
				}
			}
		}
		sort(all(d));
		ll R = -1;
		ll t = 0;
		each(i, d) {
			if(R < i->first) {
				R = i->second;
				t += R - i->first + 1;
			}else if(R < i->second) {
				t += i->second - R;
				R = i->second;
			}
		}
//		cerr << yy << ": " << endl;
//		each(i, d) cerr << i->first << ", " << i->second << endl;
//		cerr << " -> " << ((1LL << yy) - t) << endl;
//		cerr << endl;
		
		r += (1LL << yy) - t;
	}
	cout << r << endl;
	return 0;
}