QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#492977 | #9155. 集合 | A_programmer | 100 ✓ | 636ms | 20056kb | C++17 | 1.5kb | 2024-07-26 17:52:09 | 2024-07-26 17:52:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B1 = 23333333;
const ull B2 = 19260817;
const ull mod = 998244353;
const int maxn = 2e5 + 5;
const int maxm = 6e5 + 5;
int A[maxn][3], B[maxn][3];
int rpos[maxn];
ull hsh[maxm][2], mi[maxn], Ha, Hb;
ull fpow(ull a, ull b)
{
ull ans = 1;
while (b)
{
if (b & 1) ans = ans * a;
a = a * a; b >>= 1;
}
return ans;
}
void add(int pos, int op)
{
for (int i = 0; i < 3; i++)
{
Ha -= fpow(B2, hsh[A[pos][i]][0]);
(hsh[A[pos][i]][0] += (op ? mi[pos] : mod - mi[pos])) %= mod;
Ha += fpow(B2, hsh[A[pos][i]][0]);
Hb -= fpow(B2, hsh[B[pos][i]][1]);
(hsh[B[pos][i]][1] += (op ? mi[pos] : mod - mi[pos])) %= mod;
Hb += fpow(B2, hsh[B[pos][i]][1]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
mi[0] = 1; for (int i = 1; i <= n; i++) mi[i] = mi[i - 1] * B1 % mod;
for (int i = 1; i <= n; i++) cin >> A[i][0] >> A[i][1] >> A[i][2];
for (int i = 1; i <= n; i++) cin >> B[i][0] >> B[i][1] >> B[i][2];
int pos = 1; add(1, 1);
for (int i = 1; i <= n; i++)
{
while (pos < n && Ha == Hb) add(++pos, 1);
if (pos == n && Ha == Hb) rpos[i] = n + 1; else rpos[i] = pos; add(i, 0);
}
while (q--)
{
int l, r; cin >> l >> r;
cout << (r >= rpos[l] ? "No" : "Yes") << "\n";
}
return 0;
}
详细
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 7788kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 7724kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 9856kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9776kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 9776kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7672kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9732kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9776kb
Pretest #9:
score: 5
Accepted
time: 22ms
memory: 9732kb
Pretest #10:
score: 5
Accepted
time: 23ms
memory: 7720kb
Pretest #11:
score: 5
Accepted
time: 524ms
memory: 11768kb
Pretest #12:
score: 5
Accepted
time: 519ms
memory: 13952kb
Pretest #13:
score: 5
Accepted
time: 6ms
memory: 9792kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 9808kb
Pretest #15:
score: 5
Accepted
time: 113ms
memory: 7740kb
Pretest #16:
score: 5
Accepted
time: 115ms
memory: 9800kb
Pretest #17:
score: 5
Accepted
time: 54ms
memory: 7908kb
Pretest #18:
score: 5
Accepted
time: 46ms
memory: 10876kb
Pretest #19:
score: 5
Accepted
time: 636ms
memory: 13884kb
Pretest #20:
score: 5
Accepted
time: 621ms
memory: 20056kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 7676kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 7724kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 7712kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9776kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 9704kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 7712kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 9792kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9712kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 7812kb
Test #10:
score: 5
Accepted
time: 14ms
memory: 7724kb
Test #11:
score: 5
Accepted
time: 519ms
memory: 11864kb
Test #12:
score: 5
Accepted
time: 511ms
memory: 13968kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 9792kb
Test #14:
score: 5
Accepted
time: 6ms
memory: 7840kb
Test #15:
score: 5
Accepted
time: 111ms
memory: 7804kb
Test #16:
score: 5
Accepted
time: 113ms
memory: 7924kb
Test #17:
score: 5
Accepted
time: 54ms
memory: 9924kb
Test #18:
score: 5
Accepted
time: 46ms
memory: 10824kb
Test #19:
score: 5
Accepted
time: 636ms
memory: 11832kb
Test #20:
score: 5
Accepted
time: 625ms
memory: 19960kb
Extra Test:
score: 0
Extra Test Passed