Submission #2240222
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FF first
#define SS second
#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
for(auto& x: xs)
is >> x;
return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
for(unsigned int i=0;i<xs.size();++i)
os << (i?" ":"") << xs[i];
return os;
}
template<class T>
void maxi(T& x, T y){
if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 1e9+7;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
LL X, K;
cin >> X >> K;
VL rs(K+2);
REP(k,K)
cin >> rs[k+1];
rs[0] = 0;
rs[K+1] = 1e15;
LL Q;
cin >> Q;
LL lb = 0, ub = X;
LL btm = 0, top = X;
int it = 1;
while(Q--){
LL t, a;
cin >> t >> a;
while(rs[it] < t){
LL dl = rs[it] - rs[it-1];
if(it%2 == 1){ // down
if(lb < dl){
maxi(btm, min(top, btm + dl - lb));
}
ub = max(0ll, ub - dl);
lb = max(0ll, lb - dl);
}
else{ // up
if(ub+dl > X){
mini(top, max(btm, top - (ub + dl - X)));
}
ub = min(X, ub + dl);
lb = min(X, lb + dl);
}
++it;
}
LL dl = t - rs[it-1];
LL ans = 1e15;
if(a <= btm){
if(it % 2 == 1)
ans = max(0ll, lb - dl);
else
ans = min(X, lb + dl);
}
else if(top <= a){
if(it % 2 == 1)
ans = max(0ll, ub - dl);
else
ans = min(X, ub + dl);
}
else{
if(it % 2 == 1)
ans = max(0ll, a - btm + lb - dl);
else
ans = min(X, a - btm + lb + dl);
}
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Sandglass |
User |
okaduki |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2528 Byte |
Status |
AC |
Exec Time |
187 ms |
Memory |
2048 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
172 ms |
1280 KB |
1_004.txt |
AC |
178 ms |
1280 KB |
1_005.txt |
AC |
181 ms |
1280 KB |
1_006.txt |
AC |
173 ms |
1280 KB |
1_007.txt |
AC |
172 ms |
1280 KB |
1_008.txt |
AC |
182 ms |
1280 KB |
1_009.txt |
AC |
180 ms |
1280 KB |
1_010.txt |
AC |
174 ms |
1280 KB |
1_011.txt |
AC |
182 ms |
1280 KB |
1_012.txt |
AC |
179 ms |
1408 KB |
1_013.txt |
AC |
183 ms |
1536 KB |
1_014.txt |
AC |
180 ms |
1408 KB |
1_015.txt |
AC |
180 ms |
1536 KB |
1_016.txt |
AC |
177 ms |
1536 KB |
1_017.txt |
AC |
186 ms |
1536 KB |
1_018.txt |
AC |
179 ms |
1664 KB |
1_019.txt |
AC |
184 ms |
1664 KB |
1_020.txt |
AC |
180 ms |
1664 KB |
1_021.txt |
AC |
179 ms |
1536 KB |
1_022.txt |
AC |
183 ms |
1664 KB |
1_023.txt |
AC |
185 ms |
1664 KB |
1_024.txt |
AC |
180 ms |
1536 KB |
1_025.txt |
AC |
179 ms |
1792 KB |
1_026.txt |
AC |
184 ms |
1792 KB |
1_027.txt |
AC |
178 ms |
1536 KB |
1_028.txt |
AC |
179 ms |
1664 KB |
1_029.txt |
AC |
187 ms |
1920 KB |
1_030.txt |
AC |
184 ms |
1664 KB |
1_031.txt |
AC |
179 ms |
1664 KB |
1_032.txt |
AC |
185 ms |
2048 KB |
1_033.txt |
AC |
177 ms |
1152 KB |
1_034.txt |
AC |
175 ms |
1024 KB |
1_035.txt |
AC |
181 ms |
1792 KB |
1_036.txt |
AC |
172 ms |
1152 KB |
1_037.txt |
AC |
175 ms |
1152 KB |
1_038.txt |
AC |
183 ms |
1920 KB |
1_039.txt |
AC |
175 ms |
896 KB |
1_040.txt |
AC |
172 ms |
1280 KB |
1_041.txt |
AC |
184 ms |
2048 KB |