Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {

	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	args := strings.Split(sc.Text(), " ")
	n, _ := strconv.Atoi(args[0])
	t, _ := strconv.ParseInt(args[1], 10, 64)

	q, _ := strconv.Atoi(args[2])

	pos := make([]int64, n)
	direction := make([]bool, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		args = strings.Split(sc.Text(), " ")

		pos[i], _ = strconv.ParseInt(args[0], 10, 64)
		q, _ := strconv.Atoi(args[1])
		if q == 1 {
			direction[i] = true
		}
	}

	qq := make([]int, q)
	for i := 0; i < q; i++ {
		sc.Scan()
		args = strings.Split(sc.Text(), " ")

		qq[i], _ = strconv.Atoi(args[0])
	}

	ans(n, q, t, pos, direction, qq)

}

func ans(n, q int, t int64, pos []int64, dir []bool, qq []int) {

	colleation := []int64{} // syoutotu positon

	for i := 1; i < n; i++ {
		if dir[i-1] == dir[i] {
			continue
		}
		colleation = append(colleation, (pos[i-1]+pos[i])/2)

	}
	//fmt.Println(colleation)
	for i := 0; i < q; i++ {
		var ans int64
		ans = int64(-9999999)
		if dir[qq[i]-1] == true {
			// 東向きなら現ポジから＋方向で一番近い衝突点との距離を求めて、Tとの差が
			for _, v := range colleation {
				if v <= pos[qq[i]-1] {
					continue
				} else {
					// 衝突予定点が確定。衝突点との距離がT以下なら衝突点で停止
					if v-pos[qq[i]-1] <= t {
						ans = v
					} else {
						ans = pos[qq[i]-1] + int64(t)
					}
					break
				}
			}
			if ans == -9999999 {
				ans = pos[qq[i]-1] + int64((t))
			}

		} else {
			// nishi向きなら現ポジから-方向で一番近い衝突点との距離を求めて、Tとの差が
			for j := len(colleation); j > 0; j-- {
				if colleation[j-1] >= pos[qq[i]-1] {
					continue
				}
				v := colleation[j-1]
				//fmt.Printf("hoge=%d\n", v)
				// 衝突予定点が確定
				if pos[qq[i]-1]-v <= t {
					ans = v
				} else {
					ans = pos[qq[i]-1] - int64((t))
				}
				break

			}
			if ans == -9999999 {
				ans = pos[qq[i]-1] - int64((t))
			}

		}
		fmt.Printf("%d\n", ans)

	}

}

C++: #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,q,b[100010];
long long a[100010],t;
vector<long long> v;
int main(){
	cin>>n>>t>>q;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		if(i)if(b[i-1]==1&&b[i]==2)v.push_back((a[i-1]+a[i])/2);
	}
	while(q--){
		cin>>n;n--;
		int k=lower_bound(v.begin(),v.end(),a[n])-v.begin();
		if(b[n]==1){
			if(k==v.size())cout<<a[n]+t<<endl;
			else cout<<min(a[n]+t,v[k])<<endl;
		}
		else {
			if(k==0)cout<<a[n]-t<<endl;
			else cout<<max(a[n]-t,v[k-1])<<endl;
		}
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Data {
  int X, id;
  ll A;
  Data(int id, int X, ll A) : id(id), X(X), A(A){}
};

int main() {
  int N, Q;
  ll T;
  cin >> N >> T >> Q;
  ll A[N];
  int D[N];
  int X[Q];
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> D[i];
  }
  for (int i = 0; i < Q; i++) {
    cin >> X[i];
    X[i]--;
  }
  ll r = 0;
  ll l = 0;
  vector<ll> p;
  vector<Data> dr;
  vector<Data> dl;
  for (int i = 0; i < Q; i++) {
    if (D[X[i]] == 1) {
      dr.push_back(Data(i, X[i], A[X[i]]));
    } else {
      dl.push_back(Data(i, X[i], A[X[i]]));
    }
  }

  for (int i = 0; i < N; i++) {
    if (D[i] == 1) {
      r = A[i];
    } else {
      l = A[i];
    }
    if (r == 0 || l == 0) continue;
    if (abs(l - r) <= 2 * T && r < l) {
      p.push_back((l + r) / 2);
      l = 0;
      r = 0;
    }
  }
  
  int ir = 0;
  // for (ll i : p) {
  //   cout << "p: " << i << "\n";
  // }
  ll t[Q];
  for (int i = 0; i < dr.size(); i++) {
    int X = dr[i].X;
    t[dr[i].id] = A[X] + T;
    // if (X == 17) {
    //   cout << t[dr[i].id] << " ------------- " << p[ir] << "\n"; 
    // }
    while (ir < p.size()) {
      if (p[ir] < A[X]) {
        ir++;
      } else if (A[X] <= p[ir] && p[ir] <= t[dr[i].id]) {
        t[dr[i].id] = p[ir];
        break;
      } else {
        break;
      }
    }
    // if (X == 17) {
    //   cout << t[dr[i].id] << " ------------- " << ir << "\n";
    // }
  }
 

  int il = p.size() - 1;
  for (int i = dl.size() - 1; i >= 0; i--) {
    int X = dl[i].X;
    t[dl[i].id] = A[X] - T;
    while (il >= 0) {
      if (A[X] < p[il]) {
        il--;
      } else if (t[dl[i].id] <= p[il] && p[il] <= A[X]) {
        t[dl[i].id] = p[il];
        break;
      } else {
        break;
      }
    }
  }
  // for (int i = 0; i < p.size(); i++) {
  //   cout << i << " " << p[i] << "\n";
  // }

  for (ll i : t) {
    cout << i << "\n";
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
P p[100000];
vector <ll>x;


int search(ll X){
  int L=0,M,R=x.size();
  while(L<R){
    M=(L+R)/2;
    if(X<=x[M]) R=M;
    else L=M+1;
  }
  return L;
}

int main(){
  int n,T,q;
  cin>>n>>T>>q;

  int pre;
  for(int i=0,a,dir;i<n;i++){
    cin>>a>>dir;
    dir--;
    p[i]=P(a,dir);
    if(i&&pre!=dir){
      int dis=(p[i].f+p[i-1].f)/2;
      if(dis<=2*T)x.push_back(dis);
    }
    pre=dir;
  }

  //  for(int i=0;i<x.size();i++)cout <<x[i]<<" ";cout <<endl;

  while(q--){
    int Q;
    cin>>Q;
    Q--;
    ll a=p[Q].f;
    int dir=p[Q].s;
    int idx=search(a)-(dir? 1:0);
    ll ans=(dir? -1:1)*T+a;
    if(!((dir==1&&idx==-1)||(dir==0&&idx==(int)x.size()))&&abs(x[idx]-a)<=T)ans=x[idx];
    cout <<ans<<endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>

#define ALL(a) (a).begin(), (a).end()
#define llong long long
#define INF (long long)(1LL << 62)
using namespace std;

signed main(){

	llong n, T, Q;
	cin >> n >> T >> Q;

	vector<llong> a(n), d(n), q(Q);
	for(int i = 0; i < n; ++i){
		cin >> a[i] >> d[i];
	}
	for(int i = 0; i < Q; ++i){
		cin >> q[i];
	}

	vector<llong> kabe;
	kabe.push_back(-1 * INF);
	for(int i = 0; i < n - 1; ++i){
		if(d[i] == 1 && d[i+1] == 2){
			kabe.push_back((a[i] + a[i+1]) / 2);
		}
	}
	kabe.push_back(INF);

	/*
	cout << endl;
	for(auto itr = kabe.begin(); itr != kabe.end(); ++itr){
		cout << *itr << endl;
	}	
	cout << endl;
*/
	for(int i = 0; i < Q; ++i){
		int idx = q[i];
		idx--;
		if(d[idx] == 1){
			llong k = *upper_bound(kabe.begin(), kabe.end(), a[idx]);
			//cout << "debug " << k << " " << a[idx] + T << endl; 
			if(a[idx] + T >= k){
				cout << k << endl;
			}else{
				cout << a[idx] + T << endl;
			}
		}else{
			llong k = *prev(lower_bound(kabe.begin(), kabe.end(), a[idx]));
			//cout << "debug2 " << k << endl;
			if(a[idx] - T >= k){
				cout << a[idx] - T << endl;
			}else{
				cout << k << endl;
			}

		}
	}
	return 0;
}

C++: #include <stdio.h>
int main(){
  long long a[50000],T,ans[50000],stop;
  int j,k,d[50000],x[50000],Q,i,N,s;
  //in
  scanf("%d %lld %d",&N,&T,&Q);  
  for(i=0;i<N;i++){
  scanf("%lld %d",&a[i],&d[i]);
  }
  for(i=0;i<Q;i++){
    scanf("%d",&x[i]);
    x[i]--;
  }
  //in end
  for(i=0;i<Q;i++){
    s=0;
    if(d[x[i]]==1){
      for(j=x[i];j<N;j++){
	if(d[j]==2){
	  stop=(a[j]+a[j-1])/2;
	  //printf("stop %d\n",stop);
	  if(a[x[i]]+T>stop){
	  ans[i]=stop;
	  s=1;
	  break;
	  }
	}
      }
      if(s==0)ans[i]=a[x[i]]+T;
    }

    if(d[x[i]]==2){
      for(j=x[i];j>=0;j--){
	if(d[j]==1){
	  stop=(a[j]+a[j+1])/2;
	  //printf("st %d\n",stop);//
	  if(a[x[i]]-T<stop){
	  ans[i]=stop;
	  s=1;
	  break;
	  }
	}
      }
      if(s==0)ans[i]=a[x[i]]-T;
    }
  }

  for(i=0;i<Q;i++){
    printf("%lld\n",ans[i]);
  }
  return 0;
}