Submission #1602504

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>

using namespace std;

/*
  let's try computer shogi!!!
 */

struct hinge{
  long long int s; // スタート
  long long int t; // 終わり
  long long int h; // 曲がるタイミング
};

const long long int zero = 0;
long long int X;
long long int K;
vector< long long int> r;
vector<hinge> h;

long long int Q;
vector< long long int> t;
vector< long long int> a;

int main(){
  cin >> X;
  cin >> K;
  r.resize(K);
  h.resize(K+1);
  
  h[0].s = zero;
  h[0].t = X;
  h[0].h = zero;
  
  for( long long int i=0;i<K;++i){
    cin >> r[i];
  }
  r.push_back(1145141919);
  cin >> Q;
  t.resize(Q);
  a.resize(Q);
  for( long long int i=0;i<Q;++i){
    cin >> t[i];
    cin >> a[i];
  }
  
  long long int nt = 0;
  long long int qcnt = 0;
  
  for( long long int i=0;i<K+1;++i){
    long long int dt = r[i] - nt;
    
     while(nt <= t[qcnt] && t[qcnt] <= r[i] && qcnt <Q){
       long long int sand = ( a[qcnt] < h[i].h ? h[i].s : min(h[i].s + a[qcnt]-h[i].h, h[i].t));
       cerr<<nt<<","<<t[qcnt]<<","<<r[i]<<","<<i<<","<<sand<<" (nt,t,r,i,sand)"<<endl;
       if(i%2==0){
	 cout<<max(sand-(t[qcnt]-nt),zero)<<endl;
       }else{
	 cout<<min(X,sand+(t[qcnt]-nt))<<endl;
       }
       qcnt++;
     }
     
     if(i==K){continue;}
     cerr<<dt<<"(dt)"<<endl;
     if(i%2==0){
       h[i+1].s = max(h[i].s - dt,zero);
       h[i+1].t = max(h[i].t - dt,zero);
       h[i+1].h = h[i].h + max(zero, (dt - h[i].s));
     }else{
       h[i+1].s = min(X,h[i].s + dt);
       h[i+1].t = min(X,h[i].t + dt);
       h[i+1].h = h[i].h;
     }
     cerr<<h[i+1].s<<","<<h[i+1].t<<","<<h[i+1].h<<"(sth)"<<endl;
     nt = r[i];
  }
}

Submission Info

Judge Result