QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#495794 | #9155. 集合 | superguymj | 100 ✓ | 1427ms | 77736kb | C++20 | 5.2kb | 2024-07-27 23:44:17 | 2024-07-27 23:44:17 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
using namespace std;
using i64 = long long;
template<int P>
struct MInt {
int x;
MInt() : x{} {}
MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
static void setMod(int Mod_) {
Mod = Mod_;
}
int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
int val() const {
return x;
}
explicit operator int() const {
return x;
}
MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 1;
template<int P1, int P2>
struct Hash {
MInt<P1> x;
MInt<P2> y;
Hash() : x{0}, y{0} {}
Hash(int x, int y) : x{x}, y{y} {}
Hash(MInt<P1> x, MInt<P2> y) : x{x}, y{y} {}
friend Hash operator+(Hash lhs, Hash rhs) {
return Hash(lhs.x + rhs.x, lhs.y + rhs.y);
}
friend Hash operator-(Hash lhs, Hash rhs) {
return Hash(lhs.x - rhs.x, lhs.y - rhs.y);
}
friend Hash operator*(Hash lhs, Hash rhs) {
return Hash(lhs.x * rhs.x, lhs.y * rhs.y);
}
Hash &operator+=(Hash rhs) & {
x += rhs.x;
y += rhs.y;
return *this;
}
Hash &operator-=(Hash rhs) & {
x -= rhs.x;
y -= rhs.y;
return *this;
}
Hash &operator*=(Hash rhs) & {
x *= rhs.x;
y *= rhs.y;
return *this;
}
friend bool operator==(Hash lhs, Hash rhs) {
return lhs.x == rhs.x && lhs.y == rhs.y;
}
friend bool operator!=(Hash lhs, Hash rhs) {
return lhs.x != rhs.x || lhs.y != rhs.y;
}
bool operator<(const Hash &t) const {
return int(x) == int(t.x) ? int(y) < int(t.y) : int(x) < int(t.x);
}
} ;
constexpr int P1 = 1000000007, P2 = 1000000009;
using H = Hash<P1, P2>;
const H base = H(19260817, 998244353);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 3>> a(n), b(n);
rep(i,0,n-1)
{
cin >> a[i][0] >> a[i][1] >> a[i][2];
rep(j,0,2) --a[i][j];
}
rep(i,0,n-1)
{
cin >> b[i][0] >> b[i][1] >> b[i][2];
rep(j,0,2) --b[i][j];
}
vector<H> pw(n);
pw[0] = H(1, 1);
rep(i,1,n-1) pw[i] = pw[i - 1] * base;
vector<H> A(m), B(m);
map<H, int> cnt;
int tot = 0;
int p = 0;
auto ins = [&](H h, int c)
{
int &val = cnt[h];
if(val) --tot;
val += c;
if(val) ++tot;
};
vector<int> lst(n);
rep(i,0,n-1)
{
for(auto j : a[i])
{
ins(A[j], -1);
A[j] += pw[i];
ins(A[j], 1);
}
for(auto j : b[i])
{
ins(B[j], 1);
B[j] += pw[i];
ins(B[j], -1);
}
while(tot)
{
for(auto j : a[p])
{
ins(A[j], -1);
A[j] -= pw[p];
ins(A[j], 1);
}
for(auto j : b[p])
{
ins(B[j], 1);
B[j] -= pw[p];
ins(B[j], -1);
}
p++;
}
lst[i] = p;
}
while(q--)
{
int l, r;
cin >> l >> r;
--l, --r;
if(lst[r] <= l)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3628kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3568kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 3560kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3824kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3620kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3824kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 3812kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 3560kb
Pretest #9:
score: 5
Accepted
time: 16ms
memory: 3684kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 3560kb
Pretest #11:
score: 5
Accepted
time: 1246ms
memory: 77736kb
Pretest #12:
score: 5
Accepted
time: 1222ms
memory: 73000kb
Pretest #13:
score: 5
Accepted
time: 6ms
memory: 4532kb
Pretest #14:
score: 5
Accepted
time: 5ms
memory: 4204kb
Pretest #15:
score: 5
Accepted
time: 107ms
memory: 4332kb
Pretest #16:
score: 5
Accepted
time: 101ms
memory: 4556kb
Pretest #17:
score: 5
Accepted
time: 76ms
memory: 10452kb
Pretest #18:
score: 5
Accepted
time: 64ms
memory: 10560kb
Pretest #19:
score: 5
Accepted
time: 1378ms
memory: 74764kb
Pretest #20:
score: 5
Accepted
time: 1112ms
memory: 74744kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3828kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3632kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 3632kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3636kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 3632kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3796kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 3848kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 3620kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 3680kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 3852kb
Test #11:
score: 5
Accepted
time: 1322ms
memory: 73564kb
Test #12:
score: 5
Accepted
time: 1347ms
memory: 69348kb
Test #13:
score: 5
Accepted
time: 6ms
memory: 4268kb
Test #14:
score: 5
Accepted
time: 5ms
memory: 4316kb
Test #15:
score: 5
Accepted
time: 108ms
memory: 4300kb
Test #16:
score: 5
Accepted
time: 101ms
memory: 4336kb
Test #17:
score: 5
Accepted
time: 72ms
memory: 10752kb
Test #18:
score: 5
Accepted
time: 65ms
memory: 10296kb
Test #19:
score: 5
Accepted
time: 1427ms
memory: 72528kb
Test #20:
score: 5
Accepted
time: 1233ms
memory: 75616kb
Extra Test:
score: 0
Extra Test Passed