QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#535725 | #9155. 集合 | Zanite | 100 ✓ | 405ms | 14976kb | C++20 | 7.8kb | 2024-08-28 13:56:43 | 2024-08-28 13:56:44 |
Judging History
answer
// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は 僕を愛してあげたい
//
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず 脈打つこれは何だろう
//
// 何だろう...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
using namespace std;
using namespace __gnu_pbds;
// Data types
using si = short int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ld = long double;
// Pairs
using pii = pair<int, int>;
using psi = pair<si, si>;
using pll = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;
// Various outputs and debug
template<typename Z, typename = void> struct is_iterable : false_type {};
template<typename Z> struct is_iterable<Z, void_t<decltype(begin(declval<Z>())),decltype(end(declval<Z>()))>> : true_type {};
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v);
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
return os << "(" << p.fi << ", " << p.se << ")";
}
template<class TupType, size_t... I> void printTuple(ostream& os, const TupType& _tup, index_sequence<I...>) {
os << "(";
(..., (os << (I == 0? "" : ", ") << get<I>(_tup)));
os << ")";
}
template<class... Z> ostream& operator<<(ostream& os, const tuple<Z...>& _tup) {
printTuple(os, _tup, make_index_sequence<sizeof...(Z)>());
return os;
}
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v) {
os << "[";
for (auto it = v.begin(); it != v.end();) { os << *it; if (++it != v.end()) os << ", "; }
return os << "]";
}
#define debug(...) logger(cout, #__VA_ARGS__, __VA_ARGS__)
#define debugV(v, x) vlogger(cout, #v, x, v[x]);
#define rrebug(...) logger(cerr, #__VA_ARGS__, __VA_ARGS__)
#define rrebugV(v, x) vlogger(cerr, #v, x, v[x]);
template <typename... Args>
void logger(ostream& os, string vars, Args &&...values) {
os << vars << " = "; string delim = "";
(..., (os << delim << values, delim = ", "));
os << "\n";
}
template<class Y, class Z>
void vlogger(ostream& os, string var, Y idx, Z val) {
os << var << "[" << idx << "] = " << val << "\n";
}
// Various macros
#define All(x) x.begin(), x.end()
#define Sort(x) sort(All(x))
#define Reverse(x) reverse(All(x))
#define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)
// Chmin & chmax
template<typename Z> bool chmin(Z &a, Z b) { return (b < a) ? a = b, true : false; }
template<typename Z> bool chmax(Z &a, Z b) { return (b > a) ? a = b, true : false; }
// Modular arithmetic
template<int MOD>
class ModInt {
public:
int v;
ModInt() : v(0) {}
ModInt(long long _v) {
v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
if (v < 0) v += MOD;
}
friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
friend bool operator< (const ModInt &a, const ModInt &b) { return a.v < b.v; }
friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
friend bool operator> (const ModInt &a, const ModInt &b) { return a.v > b.v; }
friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }
ModInt &operator+=(const ModInt &a) { if ((v += a.v) >= MOD) v -= MOD; return *this; }
ModInt &operator-=(const ModInt &a) { if ((v -= a.v) < 0) v += MOD; return *this; }
ModInt &operator*=(const ModInt &a) { v = 1ll * v * a.v % MOD; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
friend ModInt pow(ModInt a, long long x) {
ModInt res = 1;
for (; x; x /= 2, a *= a) if (x & 1) res *= a;
return res;
}
friend ModInt inverse(ModInt a) { return pow(a, MOD - 2); }
ModInt operator+ () const { return ModInt( v); }
ModInt operator- () const { return ModInt(-v); }
ModInt operator++() const { return *this += 1; }
ModInt operator--() const { return *this -= 1; }
friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
friend istream &operator>>(istream &is, ModInt &v) { return is >> v.v; }
friend ostream &operator<<(ostream &os, const ModInt &v) { return os << v.v; }
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA = ModInt<ModA>;
using MintC = ModInt<ModC>;
// Other constants
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
const int ModH = 1'002'323'123;
using MintH = ModInt<ModH>;
const int maxN = 200'023;
const int maxM = 600'023;
const int MX = 10'000'000;
array<MintH, maxN> key = invoke([]() {
array<MintH, maxN> ret;
vector<bool> notPrime(MX, false);
for (ll i = 2, t = 0; i < MX && t < maxN; i++) {
if (!notPrime[i]) {
ret[t++] = i;
for (ll j = i*i; j < MX; j += i) notPrime[j] = true;
}
}
mt19937_64 rng(RandomSeed);
shuffle(All(ret), rng);
return ret;
});
int N, M, Q;
int A[2][3][maxN];
int l_bound[maxN];
MintH set_A[2][maxM], hsh[2];
MintH cube(MintH x) { return x * x * x; }
int main() {
scanf("%d %d %d", &N, &M, &Q);
for (int h = 0; h <= 1; h++) {
for (int i = 1; i <= N; i++) {
for (int t = 0; t < 3; t++) scanf("%d", &A[h][t][i]);
}
}
for (int h = 0; h <= 1; h++) {
for (int i = 1; i <= M; i++) {
set_A[h][i] = 1;
hsh[h] += 1;
}
}
for (int pl = 1, pr = 1; pr <= N; pr++) {
// insert pr
for (int h = 0; h <= 1; h++) {
for (int t = 0; t < 3; t++) {
MintH &cur = set_A[h][A[h][t][pr]];
hsh[h] -= cube(cur);
cur *= key[pr];
hsh[h] += cube(cur);
}
}
while (true) {
if (hsh[0] != hsh[1]) {
// remove pl
for (int h = 0; h <= 1; h++) {
for (int t = 0; t < 3; t++) {
MintH &cur = set_A[h][A[h][t][pl]];
hsh[h] -= cube(cur);
cur /= key[pl];
hsh[h] += cube(cur);
}
}
pl++;
// rrebug(pl, pr);
// for (int j = 1; j <= M; j++) rrebug(set_A[0][j], set_A[1][j]);
// rrebug(hsh[0], hsh[1]);
// cerr << "\n";
} else break;
}
l_bound[pr] = pl;
}
for (int l, r, i = 1; i <= Q; i++) {
scanf("%d %d", &l, &r);
printf("%s\n", (l >= l_bound[r]) ? "Yes" : "No");
}
}
// dibisakan
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 37ms
memory: 14736kb
Pretest #2:
score: 5
Accepted
time: 41ms
memory: 13808kb
Pretest #3:
score: 5
Accepted
time: 42ms
memory: 14740kb
Pretest #4:
score: 5
Accepted
time: 33ms
memory: 13620kb
Pretest #5:
score: 5
Accepted
time: 33ms
memory: 14976kb
Pretest #6:
score: 5
Accepted
time: 37ms
memory: 14728kb
Pretest #7:
score: 5
Accepted
time: 38ms
memory: 14292kb
Pretest #8:
score: 5
Accepted
time: 41ms
memory: 14808kb
Pretest #9:
score: 5
Accepted
time: 67ms
memory: 13740kb
Pretest #10:
score: 5
Accepted
time: 63ms
memory: 14736kb
Pretest #11:
score: 5
Accepted
time: 269ms
memory: 14720kb
Pretest #12:
score: 5
Accepted
time: 272ms
memory: 14740kb
Pretest #13:
score: 5
Accepted
time: 39ms
memory: 14472kb
Pretest #14:
score: 5
Accepted
time: 39ms
memory: 13472kb
Pretest #15:
score: 5
Accepted
time: 172ms
memory: 14008kb
Pretest #16:
score: 5
Accepted
time: 175ms
memory: 14300kb
Pretest #17:
score: 5
Accepted
time: 58ms
memory: 13820kb
Pretest #18:
score: 5
Accepted
time: 58ms
memory: 13824kb
Pretest #19:
score: 5
Accepted
time: 395ms
memory: 14736kb
Pretest #20:
score: 5
Accepted
time: 386ms
memory: 14764kb
Final Tests
Test #1:
score: 5
Accepted
time: 42ms
memory: 14484kb
Test #2:
score: 5
Accepted
time: 41ms
memory: 14932kb
Test #3:
score: 5
Accepted
time: 34ms
memory: 14736kb
Test #4:
score: 5
Accepted
time: 34ms
memory: 14312kb
Test #5:
score: 5
Accepted
time: 42ms
memory: 13524kb
Test #6:
score: 5
Accepted
time: 34ms
memory: 13880kb
Test #7:
score: 5
Accepted
time: 38ms
memory: 13876kb
Test #8:
score: 5
Accepted
time: 41ms
memory: 13944kb
Test #9:
score: 5
Accepted
time: 68ms
memory: 14008kb
Test #10:
score: 5
Accepted
time: 66ms
memory: 14732kb
Test #11:
score: 5
Accepted
time: 268ms
memory: 14964kb
Test #12:
score: 5
Accepted
time: 271ms
memory: 14812kb
Test #13:
score: 5
Accepted
time: 40ms
memory: 14736kb
Test #14:
score: 5
Accepted
time: 39ms
memory: 14732kb
Test #15:
score: 5
Accepted
time: 174ms
memory: 14340kb
Test #16:
score: 5
Accepted
time: 178ms
memory: 13536kb
Test #17:
score: 5
Accepted
time: 58ms
memory: 13668kb
Test #18:
score: 5
Accepted
time: 62ms
memory: 14528kb
Test #19:
score: 5
Accepted
time: 399ms
memory: 14680kb
Test #20:
score: 5
Accepted
time: 405ms
memory: 14964kb
Extra Test:
score: 0
Extra Test Passed