Submission #02388

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int64, int64 > Pi;
const int64 INF = 3000000000000000000LL;
  
int64 N, T, Q;
vector< Pi > data;
int64 dp[100002];
  
int64 rec(int idx, const int d)
{
  if(~dp[idx]) {
    return(dp[idx]);
  } else if(data[idx].second != data[idx + d].second) {
    return(dp[idx] = (data[idx].first + data[idx + d].first) / 2LL);
  } else {
    return(dp[idx] = rec(idx + d, d));
  }
}
  
int main()
{
  memset(dp, -1, sizeof(dp));
  cin >> N >> T >> Q;
  data.push_back(Pi(-INF, 1));
  for(int i = 0; i < N; i++) {
    int64 A, D;
    cin >> A >> D;
    data.push_back(Pi(A, D));
  }
  data.push_back(Pi(INF, 2));
  while(Q--) {
    int64 X;
    cin >> X;
    if(data[X].second == 1) cout << min(data[X].first + T, rec(X, 1)) << endl;
    else                   cout << max(data[X].first - T, rec(X, -1)) << endl;
  }
}

ステータス

項目	データ
問題	0260 - JOI国のお散歩事情 (Walking in JOI Kingdom)
ユーザー名	ei1333
投稿日時	2015-12-16 17:14:56
言語	C++11
状態	Accepted
得点	5
ソースコード長	930 Byte
最大実行時間	92 ms
最大メモリ使用量	4584 KB

セット

	セット	得点	Cases
1	INPUT1	1 / 1	*in1.txt
2	INPUT2	1 / 1	*in2.txt
3	INPUT3	1 / 1	*in3.txt
4	INPUT4	1 / 1	*in4.txt
5	INPUT5	1 / 1	*in5.txt

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
2016-yo-t4-in1.txt	AC	26 ms	1240 KB	1
2016-yo-t4-in2.txt	AC	31 ms	1460 KB		2
2016-yo-t4-in3.txt	AC	65 ms	3892 KB			3
2016-yo-t4-in4.txt	AC	92 ms	3432 KB				4
2016-yo-t4-in5.txt	AC	85 ms	4584 KB					5
2016-yo-t4-in_s1.txt	AC	19 ms	1208 KB
2016-yo-t4-in_s2.txt	AC	18 ms	1304 KB