QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745097 | #6439. Cloud Retainer's Game | maspy | AC ✓ | 524ms | 15776kb | C++23 | 7.7kb | 2024-11-14 04:10:36 | 2024-11-14 04:10:37 |
Judging History
answer
#line 2 "/home/maspy/library/my_template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ll8 = __int128;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template <class T> using vvvvvc = vector<vvvvc<T>>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
IN(name)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i))
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i))
#define FORIN(x, A) for (auto&& x : A)
#define FOR_nCk(s, n, k) \
for (ll s = (1 << k) - 1, tmp_var = 0; s < (1 << n); \
tmp_var = s | (s - 1), s = (tmp_var + 1) | (((~tmp_var & -~tmp_var) - 1) >> (__builtin_ctz(s) + 1)))
#define FOR_SUB(t, s) for(ll t = s; t >= 0; t = (t==0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
using ull = unsigned long long;
using uint = unsigned int;
int popcnt(uint x) {
return __builtin_popcount(x);
}
int popcnt(int x) {
return __builtin_popcount(x);
}
int popcnt(ull x) {
return __builtin_popcountll(x);
}
int popcnt(ll x) {
return __builtin_popcountll(x);
}
int bsr(uint x) {
return 31 - __builtin_clz(x);
}
int bsr(ull x) {
return 63 - __builtin_clzll(x);
}
int ctz(int x) {
return __builtin_ctz(x);
}
int ctz(ll x) {
return __builtin_ctzll(x);
}
int ctz(ull x) {
return __builtin_ctzll(x);
}
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
ll ceil(ll x, ll y) {
assert(y >= 1);
return (x > 0 ? (x + y - 1) / y : x / y);
}
ll floor(ll x, ll y) {
assert(y >= 1);
return (x > 0 ? x / y : (x - y + 1) / y);
}
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
long double __VA_ARGS__; \
IN(__VA_ARGS__)
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
scan(head);
IN(tail...);
}
ll isqrt(ll n) {
ll x = n, y = (n + 1) / 2;
while (y < x) { tie(x, y) = mp(y, (y + n / y) / 2); }
return x;
}
vi s_to_vi(string S, char first_char='a'){
vi A(S.size());
FOR(i, S.size()){
A[i] = S[i] - first_char;
}
return A;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& A) {
os << A.fi << " " << A.se;
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& A) {
for (size_t i = 0; i < A.size(); i++) {
if(i) os << " ";
os << A[i];
}
return os;
}
void print() {
cout << "\n";
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
cout << head;
if (sizeof...(Tail)) cout << " ";
print(forward<Tail>(tail)...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename T>
vector<T> cumsum(vector<T> A) {
ll N = A.size();
vector<T> B(N + 1);
B[0] = T(0);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
return B;
}
vi bin_count(vi& A, ll size) {
vi C(size);
for (auto&& x : A) {
++C[x];
}
return C;
}
template <typename T>
vi argsort(vector<T>& A){
vi ids(A.size());
iota(all(ids), 0);
sort(all(ids), [&](ll i, ll j){
return A[i] < A[j] || (A[i] == A[j] && i < j);
});
return ids;
}
ll binary_search(function<bool(ll)> check, ll ok, ll ng) {
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
if (check(x))
ok = x;
else
ng = x;
}
return ok;
}
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
template <typename T>
vc<T> merge_sort(vc<T>& A, vc<T>& B) {
vc<T> C;
C.reserve(A.size() + B.size());
merge(all(A), all(B), back_inserter(C));
return C;
}
#line 2 "main.cpp"
void solve() {
LL(H);
// x, y, タイプ (in 01)
using T = tuple<ll, ll, ll>;
vc<T> pts;
LL(N);
FOR(_, N) {
LL(x, y);
pts.eb(x, y, 0);
}
LL(M);
FOR(_, M) {
LL(x, y);
pts.eb(x, y, 1);
}
sort(all(pts));
auto mod = [&](ll a) -> ll {
a %= (H + H);
if (a < 0) a += H + H;
return a;
};
/*
・y=x+k mod 2H のところを飛んでいる dp value
*/
const ll INF = 1LL << 60;
map<ll, ll> DP;
DP[0] = 0;
FOR(i, N + M) {
auto [x, y, t] = pts[i];
ll dp1 = -INF, dp2 = -INF;
ll a = mod(y - x), b = mod(H + H - y - x);
if (DP.count(a)) dp1 = DP[a];
if (DP.count(b)) dp2 = DP[b];
if (t == 0) {
ll dp = max(dp1, dp2);
DP[a] = dp;
DP[b] = dp;
} else {
if (dp1 >= 0) DP[a]++;
if (dp2 >= 0) DP[b]++;
}
}
ll ANS = 0;
FORIN(p, DP) chmax(ANS, p.se);
print(ANS);
}
signed main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(15);
LL(T);
FOR(_, T) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
2 4 3 1 1 2 2 6 2 4 3 1 3 3 5 1 7 3 3 1 4 2 3 1 1 6 2 9 1
output:
3 3
result:
ok 2 number(s): "3 3"
Test #2:
score: 0
Accepted
time: 311ms
memory: 15776kb
input:
5503 10 19 2 4 2 8 8 3 8 4 8 7 2 7 2 6 1 5 3 2 6 4 2 1 4 5 2 5 7 1 4 7 5 7 2 2 8 6 8 1 12 5 1 4 8 5 2 6 1 3 6 1 1 1 7 7 2 5 6 6 8 1 2 3 5 10 5 9 5 10 7 6 6 5 7 1 3 9 6 8 8 8 6 4 2 9 5 4 4 2 10 9 2 3 2 1 7 1 4 3 14 4 6 6 1 2 1 7 6 2 3 4 4 5 3 6 5 1 4 3 4 3 2 6 2 8 6 8 2 6 6 5 2 5 1 3 1 2 3 7 4 5 5 3 ...
output:
2 1 2 1 3 2 0 2 4 6 1 2 0 0 1 2 1 1 0 1 0 0 2 1 1 3 2 3 3 2 1 2 0 1 5 1 1 1 0 1 3 1 2 3 3 3 2 1 0 3 1 2 2 0 4 1 1 0 1 2 2 2 1 1 1 1 2 3 2 2 2 1 1 3 1 3 0 0 3 4 5 1 1 1 1 1 0 2 0 0 3 0 2 1 1 1 0 3 2 1 3 4 3 2 2 4 2 4 2 1 2 1 0 1 3 0 3 0 2 1 0 2 5 1 2 2 1 0 1 3 0 2 3 1 4 2 2 0 2 3 2 0 0 3 1 1 1 1 3 2 ...
result:
ok 5503 numbers
Test #3:
score: 0
Accepted
time: 524ms
memory: 15268kb
input:
54 83 1995 54 14 42 63 23 55 46 52 94 71 16 18 51 54 62 47 90 38 42 50 82 20 8 28 52 64 49 19 56 5 10 74 99 30 90 42 48 2 11 78 4 38 78 77 26 26 47 12 82 60 41 17 87 2 37 16 51 15 32 63 88 82 76 33 44 10 94 28 31 5 30 80 29 19 35 70 88 78 39 69 40 5 84 52 87 59 54 36 34 76 88 42 42 37 79 70 27 77 19...
output:
47 32 32 32 38 32 39 33 39 40 36 32 36 32 46 30 35 41 40 36 108 90 98 81 166 115 106 170 148 113 198 72 57 202 337 153 186 978 87 886 151 489 111 112 90 154 174 188 266 59 10210 1041 87 981
result:
ok 54 numbers