Submission #1563945
Source Code Expand
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cassert>
using namespace std;
#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll>
#define VVI vector<vector<ll> >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define PRINT1(table, D0) REP(d0, D0) cout<<table[d0]<<" "; cout<<"\n";
#define PRINT2(table, D0, D1) REP(d0, D0) { REP(d1, D1) cout<<table[d0][d1]<<" "; cout<<"\n"; }
#define PRINT3(table, D0, D1, D2) REP(d0, D0) { REP(d1, D1) { REP(d2, D2) cout<<table[d0][d1][d2]<<" "; cout<<"\n"; } cout<<"\n"; }
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b)
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b)
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
#define MOD 1000000007LL
#define INF (1LL<<60)
struct M {
ll ah, ch, al, cl;
};
ostream& operator<<(ostream& os, const M& m) {
os<<m.ah<<" "<<m.ch<<" "<<m.al<<" "<<m.cl<<endl;
return os;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
ll X,K,Q;
while(cin>>X>>K) {
VI r(K+2);
REP(i, K) cin>>r[i+1];
r[K+1] = 1LL<<60;
vector<M> ms;
ms.push_back(M{X, X, 0, 0});
RANGE(i, 1, K+2) {
ll sign = (i-1)%2==0 ? -1 : 1;
M& p = ms[i-1];
M m;
ll nh = p.ch + sign * (r[i]-r[i-1]);
ll nl = p.cl + sign * (r[i]-r[i-1]);
m.ch = min(max(nh, 0LL), X);
m.cl = min(max(nl, 0LL), X);
m.ah = p.ah;
// DD(nh);
if(nh>X) m.ah -= nh-X;
if(nh<0) m.ah += -nh;
m.al = p.al;
if(nl>X) m.al -= nl-X;
if(nl<0) m.al += -nl;
ms.push_back(m);
}
// DD(ms);
cin>>Q;
REP(qi, Q) {
ll T, A;
cin>>T>>A;
ll i = max<ll>(1, distance(r.begin(), lower_bound(ALL(r), T)));
// DD(i);
// RANGE(i, 1, K+2) {
// if(T <= r[i]) {
// between i-1 and i
// DD(i);
ll sign = (i-1)%2==0 ? -1 : 1;
// DD(sign);
// DD(T-r[i-1]);
// DD(ms[i-1].ah-A);
// DD(max(ms[i-1].ch - max(ms[i-1].ah-A, ms[i-1].al), 0LL));
ll v = ms[i-1].ch - (ms[i-1].ah - min(max(A, ms[i-1].al), ms[i-1].ah)) + sign * (T-r[i-1]);
v = max(min(v, X), 0LL);
cout<<v<<endl;
// break;
// }
// }
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Sandglass |
User |
kojingharang |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
4029 Byte |
Status |
AC |
Exec Time |
192 ms |
Memory |
7152 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 |
180 ms |
6000 KB |
1_004.txt |
AC |
181 ms |
6384 KB |
1_005.txt |
AC |
189 ms |
6896 KB |
1_006.txt |
AC |
181 ms |
6128 KB |
1_007.txt |
AC |
180 ms |
6896 KB |
1_008.txt |
AC |
186 ms |
5872 KB |
1_009.txt |
AC |
181 ms |
5488 KB |
1_010.txt |
AC |
180 ms |
6512 KB |
1_011.txt |
AC |
183 ms |
6640 KB |
1_012.txt |
AC |
178 ms |
7024 KB |
1_013.txt |
AC |
182 ms |
5488 KB |
1_014.txt |
AC |
182 ms |
6512 KB |
1_015.txt |
AC |
181 ms |
6128 KB |
1_016.txt |
AC |
181 ms |
5872 KB |
1_017.txt |
AC |
183 ms |
6000 KB |
1_018.txt |
AC |
182 ms |
6384 KB |
1_019.txt |
AC |
182 ms |
5232 KB |
1_020.txt |
AC |
187 ms |
7152 KB |
1_021.txt |
AC |
184 ms |
7024 KB |
1_022.txt |
AC |
184 ms |
6000 KB |
1_023.txt |
AC |
190 ms |
6512 KB |
1_024.txt |
AC |
181 ms |
7024 KB |
1_025.txt |
AC |
190 ms |
5744 KB |
1_026.txt |
AC |
191 ms |
7024 KB |
1_027.txt |
AC |
186 ms |
5488 KB |
1_028.txt |
AC |
187 ms |
6384 KB |
1_029.txt |
AC |
186 ms |
6128 KB |
1_030.txt |
AC |
187 ms |
5616 KB |
1_031.txt |
AC |
185 ms |
5744 KB |
1_032.txt |
AC |
190 ms |
7024 KB |
1_033.txt |
AC |
169 ms |
1152 KB |
1_034.txt |
AC |
171 ms |
1152 KB |
1_035.txt |
AC |
188 ms |
6640 KB |
1_036.txt |
AC |
173 ms |
1152 KB |
1_037.txt |
AC |
175 ms |
1152 KB |
1_038.txt |
AC |
190 ms |
6640 KB |
1_039.txt |
AC |
171 ms |
896 KB |
1_040.txt |
AC |
177 ms |
1280 KB |
1_041.txt |
AC |
192 ms |
6640 KB |