QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#504287 | #9155. 集合 | Bitter | 100 ✓ | 404ms | 30072kb | C++14 | 3.3kb | 2024-08-04 11:31:30 | 2024-08-04 11:31:32 |
Judging History
answer
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb emplace_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
w = -1;
ch = getchar();
}
while (isdigit(ch)) {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
const int base1 = 3;
const int base2 = 7;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 7;
const int N = 6e5 + 10;
int h1[N], h2[N], pw1[N], pw2[N];
int H1[N], H2[N];
inline int Add(int x, int y, int op = 0) {
if(!op) return (x + y) % mod1;
return (x + y) % mod2;
}
inline int Mul(int x, int y, int op = 0) {
if(!op) return 1ll * x * y % mod1;
return 1ll * x * y % mod2;
}
int n, a[N][3], m, q, b[N][3];
int A1, B1, A2, B2;
unsigned long long a1, b1, a2, b2;
int rig[N];
inline int insert(int p) {
if(p > n) return 0;
for(int i = 0; i < 3; ++i) {
int u = a[p][i];
A1 ^= h1[u];
A2 ^= h2[u];
a1 -= h1[u];
a2 -= h2[u];
h1[u] = Add(h1[u], pw1[p]);
h2[u] = Add(h2[u], pw2[p], 1);
A1 ^= h1[u];
A2 ^= h2[u];
a2 += h2[u];
a1 += h1[u];
}
for(int i = 0; i < 3; ++i) {
int u = b[p][i];
b1 -= H1[u];
b2 -= H2[u];
B1 ^= H1[u];
B2 ^= H2[u];
H1[u] = Add(H1[u], pw1[p]);
H2[u] = Add(H2[u], pw2[p], 1);
B1 ^= H1[u];
B2 ^= H2[u];
b1 += H1[u];
b2 += H2[u];
}
return A1 == B1 && A2 == B2 && a1 == b1 && a2 == b2;
}
inline int del(int p) {
if(p > n) return 0;
for(int i = 0; i < 3; ++i) {
int u = a[p][i];
A1 ^= h1[u];
A2 ^= h2[u];
a1 -= h1[u];
a2 -= h2[u];
h1[u] = Add(h1[u], mod1 - pw1[p]);
h2[u] = Add(h2[u], mod2 - pw2[p], 1);
A1 ^= h1[u];
A2 ^= h2[u];
a2 += h2[u];
a1 += h1[u];
}
for(int i = 0; i < 3; ++i) {
int u = b[p][i];
B1 ^= H1[u];
B2 ^= H2[u];
b1 -= H1[u];
b2 -= H2[u];
H1[u] = Add(H1[u], mod1 - pw1[p]);
H2[u] = Add(H2[u], mod2 - pw2[p], 1);
B1 ^= H1[u];
B2 ^= H2[u];
b1 += H1[u];
b2 += H2[u];
}
return A1 == B1 && A2 == B2 && a1 == b1 && a2 == b2;
}
mt19937 rnd(time(0));
unsigned long long msk;
inline int rd(int x) {
x = x * 1ull;
x ^= msk;
x ^= (x << 7);
x ^= (x >> 11);
x ^= (x << 13);
if(x < 0) x = -x;
x %= mod1;
return x;
}
int main() {
n = read(), m = read(), q = read();
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < 3; ++j) a[i][j] = read();
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < 3; ++j) b[i][j] = read();
}
int test = 10;
while(test--) {
msk = rnd();
pw1[0] = pw2[0] = 1;
for(int i = 1; i <= 600000; ++i) {
pw1[i] = Mul(pw1[i - 1], base1);
pw2[i] = Mul(pw2[i - 1], base2, 1);
}
for(int i = 1; i <= 600000; ++i) {
pw1[i] = Mul(pw1[i], i);
pw2[i] = Mul(pw2[i], i, 1);
pw1[i] = Add(pw1[i], rd(i));
pw2[i] = Add(pw2[i], rd(i), 1);
}
int r = 1;
a1 = b1 = a2 = b2 = A1 = B1 = A2 = B2 = 0;
for(int i = 1; i <= n; ++i) {
h1[i] = h2[i] = H1[i] = H2[i] = 0;
}
for(int l = 1; l <= n; ++l) {
while(r <= n && insert(r)) r = r + 1;
if(!rig[l]) rig[l] = r - 1;
else {
rig[l] = min(rig[l], r - 1);
}
if(r <= n) del(r);
del(l);
}
}
while(q--) {
int ql = read(), qr = read();
if(qr <= rig[ql]) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
詳細信息
Pretests
Pretest #1:
score: 5
Accepted
time: 58ms
memory: 20052kb
Pretest #2:
score: 5
Accepted
time: 62ms
memory: 22240kb
Pretest #3:
score: 5
Accepted
time: 61ms
memory: 20144kb
Pretest #4:
score: 5
Accepted
time: 57ms
memory: 20016kb
Pretest #5:
score: 5
Accepted
time: 58ms
memory: 22184kb
Pretest #6:
score: 5
Accepted
time: 65ms
memory: 22100kb
Pretest #7:
score: 5
Accepted
time: 62ms
memory: 20132kb
Pretest #8:
score: 5
Accepted
time: 61ms
memory: 20016kb
Pretest #9:
score: 5
Accepted
time: 71ms
memory: 22192kb
Pretest #10:
score: 5
Accepted
time: 72ms
memory: 20084kb
Pretest #11:
score: 5
Accepted
time: 309ms
memory: 26944kb
Pretest #12:
score: 5
Accepted
time: 312ms
memory: 26992kb
Pretest #13:
score: 5
Accepted
time: 69ms
memory: 20156kb
Pretest #14:
score: 5
Accepted
time: 68ms
memory: 20192kb
Pretest #15:
score: 5
Accepted
time: 117ms
memory: 22108kb
Pretest #16:
score: 5
Accepted
time: 113ms
memory: 22068kb
Pretest #17:
score: 5
Accepted
time: 90ms
memory: 22120kb
Pretest #18:
score: 5
Accepted
time: 86ms
memory: 20080kb
Pretest #19:
score: 5
Accepted
time: 373ms
memory: 26976kb
Pretest #20:
score: 5
Accepted
time: 403ms
memory: 30072kb
Final Tests
Test #1:
score: 5
Accepted
time: 66ms
memory: 22152kb
Test #2:
score: 5
Accepted
time: 66ms
memory: 20060kb
Test #3:
score: 5
Accepted
time: 61ms
memory: 20016kb
Test #4:
score: 5
Accepted
time: 58ms
memory: 20056kb
Test #5:
score: 5
Accepted
time: 58ms
memory: 20132kb
Test #6:
score: 5
Accepted
time: 66ms
memory: 20052kb
Test #7:
score: 5
Accepted
time: 62ms
memory: 20056kb
Test #8:
score: 5
Accepted
time: 58ms
memory: 22236kb
Test #9:
score: 5
Accepted
time: 76ms
memory: 20192kb
Test #10:
score: 5
Accepted
time: 76ms
memory: 19992kb
Test #11:
score: 5
Accepted
time: 313ms
memory: 26976kb
Test #12:
score: 5
Accepted
time: 313ms
memory: 29160kb
Test #13:
score: 5
Accepted
time: 64ms
memory: 20140kb
Test #14:
score: 5
Accepted
time: 59ms
memory: 20200kb
Test #15:
score: 5
Accepted
time: 115ms
memory: 22188kb
Test #16:
score: 5
Accepted
time: 124ms
memory: 20140kb
Test #17:
score: 5
Accepted
time: 90ms
memory: 20088kb
Test #18:
score: 5
Accepted
time: 87ms
memory: 24316kb
Test #19:
score: 5
Accepted
time: 366ms
memory: 29028kb
Test #20:
score: 5
Accepted
time: 404ms
memory: 30040kb
Extra Test:
score: 0
Extra Test Passed