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 <vector>
#include <algorithm>
#include <utility>
constexpr long long INF = 2e18 + 100;

using namespace std;
int main(){
  long long N, T, Q;
  cin >> N >> T >> Q;
  vector<pair<long long,int>> V;
  for(int i = 0; i < N; ++i){
    long long a, d;
    cin >> a >> d;
    V.emplace_back(a,d);
  }
  vector<int> X(Q);
  for(int i = 0; i < Q; ++i) cin >> X[i], --X[i];
  vector<long long> W;
  for(int i = 1; i < N; ++i){
    if(V[i].second == 2 and V[i-1].second == 1){
      // cerr << i << endl;
      long long m = (V[i].first+V[i-1].first)/2;
      W.emplace_back(m);
    }
  }
  W.emplace_back(INF);
  W.emplace_back(-INF);
  sort(W.begin(),W.end());
  for(int i = 0; i < Q; ++i){
    long long a = V[X[i]].first;
    long long a_ = V[X[i]].first;
    if(V[X[i]].second == 1){
      a_ += T;
      int idx = upper_bound(W.begin(),W.end(),a) - W.begin();
      long long w = W[idx];
      // cerr << a << " " << a_ << " " << w << endl;
      // if(w >= a) a_ = w;
      // cout << a_ << endl;
      cout << min(w, a_) << endl;
    }else{
      a_ -= T;
      int idx = upper_bound(W.begin(),W.end(),a) - W.begin() - 1;
      long long w = W[idx];
      // if(w >= a) a_ = w;
      // cout << a_ << endl;
      cout << max(w, a_) << endl;
    }
  }
}

C++: #include<iostream>
#include<string>
#include<cstdio>

using namespace std;
long long int home[50002] = { 0 };
long long int home2[50002] = { 0 };
int keyman[1005] = { 0 };
long long int walk[2][50002] = { 0 };
long long int walk2[2][50002] = { 0 };
int main() {
	long long int n, t;
	int q;
	scanf("%lld %lld %d", &n, &t, &q);

	for (int i = 0; i < n; i++) {
		if (i < 50002) {
			scanf("%lld %lld", &walk[0][i], &home[i]);
		}
		else {
			int j = i - 50002;
			scanf("%lld %lld", &walk2[0][j], &home2[j]);
		}
	}
	for (int i = 0; i <q; i++) {
		scanf_s("%lld", &keyman[i]);
	}

	for (int i = 1; i <= t; i++) {
		for (int j = 0; j < n; j++) {
			if (j < 50002) {
				if (walk[1][j] != 1) {
					if (home[j] == 1) {
						walk[0][j]++;
					}
					else {
						walk[0][j]--;
					}

				}
				for (int k = 0; k < j; k++) {

					if (walk[0][k] == walk[0][j]) {
						walk[1][k] = 1;
						walk[1][j] = 1;
					}
				}
			}
			else {
				int u = j - 50002;
				if (walk2[1][u] != 1) {
					if (home2[u] == 1) {
						walk2[0][u]++;
					}
				else {
					walk2[0][u]--;
					}

				}
				for (int k = 0; k < j; k++) {
					if(k<50002){
						if (walk[0][k] == walk2[0][u]) {
							walk[1][k] = 1;
							walk2[1][u] = 1;
						}
					}
					else {
						int r = k - 50002;
						if (walk2[0][r] == walk2[0][u]) {
							walk2[1][r] = 1;
							walk2[1][u] = 1;
						}

					}
				}
			}
			
			/*cout << "nowspot" << walk[0][j] << endl;*/
		}
		/*for (int x = 0; x < n; x++) {
			if (walk[1][x] == 1) {
				cout << "freeze:" << x << endl;
			}
		}
		*/
	}
	for (int i = 0; i < q; i++) {
		if (keyman[i] < 50003) {
			printf("%lld\n", walk[0][keyman[i] - 1]);
		}
		else {
			printf("%lld\n", walk2[0][keyman[i] - 50003]);
		}
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int ord(int a, int p) {
	if (a%p == 0) {
		return ord(a / p, p) + 1;
	}
	else {
		return 0;
	}
}
long long ruin(int a, int n, long long  p) {
	if (n == 0) {
		return (1%p);
	}
	else {
	long long x = ruin(a, (n - (n % 2)) / 2, p);
		if (n % 2 == 0) {
			return (x*x) % p;
		}
		else {
			return (((x*x) % p)*a) % p;
			
		}
	
	}
	
}
long long com(int n, int r, int p) {
	if (r == 0) {
		return (1%p);
	}
	else {
		long long x = com(n, r - 1, p);
		return (x*(n - r) / r) % p;
	}
}
int main()
{
	int n, q; long long t;
	cin >> n >> t >> q;
	vector<long long> a(n);
	vector<int> d(n);
	vector<int> e(q);
	vector<long long>ans(q);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> d[i];
	}
	for (int i = 0; i < q; i++) {
		int x;
		cin >> x;
		e[i] = x - 1;
	}
	int ba = 2;
	vector<int> nu(n);
	vector<int> ch(n);
	int si = 0;
	int no = -1;//kesu
	for (int i = 0; i < n; i++)
	{
		if (d[i] != ba) {
			ch[si] = i;
			si++;
			no++;
			ba = d[i];
		}
		nu[i] = no;
	}
	for (int i = 0; i < q; i++) {
		int p = e[i];
		int x = nu[p];
		int y = x + (1 - ((x+2) % 2));
		if (y < 0) {
			cout << a[p] - t << endl;
		}
		else if (y >= si) {
			cout << a[p] + t << endl;
		}
		else {
			long long me = (a[ch[y]] + a[ch[y] - 1]) / 2;
			if (d[p] == 1) {
				cout << min(a[p] + t, me) << endl;
			}
			else {
				cout << max(a[p] - t, me) << endl;
			}
		}
	}
}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 100000005
#define MAX 5001
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[1002][1002];
int dp[1002][1002];
int main(){
	int h, w, n;
	while(1){
		scanf("%d%d%d", &h, &w, &n);
		if(!h)break;
		fill((int*)a, (int*)(a+1002), 0);
		fill((int*)dp, (int*)(dp+1002), 0);
		for(int i = 1;i <= h;i++)
		for(int j = 1;j <= w;j++)scanf("%d", &a[i][j]);
		n--;dp[1][1] = n;
		for(int i = 1;i <= h;i++){
			for(int j = 1;j <= w;j++){
				dp[i][j] += dp[i][j-1]/2;
				if(a[i][j-1] == 1)dp[i][j] += dp[i][j-1]%2;
				dp[i][j] += dp[i-1][j]/2;
				if(a[i-1][j] == 0)dp[i][j] += dp[i-1][j]%2;
			}
		}
		
		int y = 1, x = 1, t, f;
		while(y <= h && x <= w){
			f = a[y][x];
			if(dp[y][x]%2)f = !f;
			if(!f)y++;
			else x++;
		}
		printf("%d %d\n", y, x);
	}
	return 0;
}