Submission #1792959

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


const int MAX = 210000;
long long X;
int K, Q;
long long R[MAX];
long long T[MAX], A[MAX];

long long leftX[MAX], leftY[MAX], rightX[MAX], rightY[MAX];

// r: 偶数～ down, 奇数～ up

int main() {
	while (cin >> X >> K) {
		R[0] = 0;
		for (int i = 0; i < K; ++i) cin >> R[i+1];
		++K;
		cin >> Q;
		for (int i = 0; i < Q; ++i) cin >> T[i] >> A[i];

		leftX[0] = 0, leftY[0] = 0, rightX[0] = X, rightY[0] = X;
		for (int r = 0; r < K - 1; ++r) {
			long long diff = R[r + 1] - R[r];
			leftX[r + 1] = leftX[r], leftY[r + 1] = leftY[r], rightX[r + 1] = rightX[r], rightY[r + 1] = rightY[r];
			if (r % 2 == 0) {
				if (leftY[r] >= diff) leftY[r + 1] -= diff, rightY[r + 1] -= diff;
				else if (rightY[r] >= diff) leftX[r + 1] += diff - leftY[r], leftY[r + 1] = 0, rightY[r + 1] -= diff;
				else leftX[r + 1] = rightX[r], leftY[r + 1] = 0, rightY[r + 1] = 0;
			}
			else {
				if (X - rightY[r] >= diff) leftY[r + 1] += diff, rightY[r + 1] += diff;
				else if (X - leftY[r] >= diff) leftY[r + 1] += diff, rightX[r + 1] -= diff - (X - rightY[r]), rightY[r + 1] = X;
				else leftY[r + 1] = X, rightX[r + 1] = leftX[r], rightY[r + 1] = X;
			}
			//cout << r + 1 << " (" << R[r + 1] << "): " << make_pair(leftX[r + 1], leftY[r + 1]) << ", " << make_pair(rightX[r + 1], rightY[r + 1]) << endl;
		}

		for (int i = 0; i < Q; ++i) {
			int it = upper_bound(R, R + K, T[i]) - R;
			--it;
			long long diff = T[i] - R[it];
			long long cur = 0;
			if (A[i] <= leftX[it]) cur = leftY[it];
			else if (A[i] >= rightX[it]) cur = rightY[it];
			else cur = leftY[it] + (A[i] - leftX[it]);

			if (it % 2 == 0) {
				cur -= diff;
				chmax(cur, 0LL);
			}
			else {
				cur += diff;
				chmin(cur, X);
			}
			//cout << it << ", " << R[it] << ", " << make_pair(leftX[it], leftY[it]) << ", " << make_pair(rightX[it], rightY[it]) << ", " << diff << ", " <<  cur << endl;
			cout << cur << endl;
		}
	}
}

Submission Info

Judge Result