QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#606208 | #9155. 集合 | Jerrywang | 100 ✓ | 205ms | 20176kb | C++14 | 1.3kb | 2024-10-02 23:14:11 | 2024-10-02 23:14:11 |
Judging History
answer
// Title: 集合
// Source: NOI2024
// Author: Jerrywang
#include <bits/stdc++.h>
#define ll unsigned long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=200010, M=N*3;
using namespace std;
mt19937_64 rnd(time(0));
int n, m, T, a[N][3], b[N][3], rp[N];
ll h[N], suma, sumb, seta[M], setb[M];
ll Rnd(ll x)
{
return x*131+x*x*233+x*x*x*57257;
}
void modify(int i, int d)
{
rep(j, 0, 2)
{
int x=a[i][j];
suma-=Rnd(seta[x]);
seta[x]+=h[i]*d;
suma+=Rnd(seta[x]);
}
rep(j, 0, 2)
{
int x=b[i][j];
sumb-=Rnd(setb[x]);
setb[x]+=h[i]*d;
sumb+=Rnd(setb[x]);
}
}
int main()
{
#ifdef Jerrywang
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%d", &n, &m, &T);
rep(i, 1, n) h[i]=rnd();
rep(i, 1, n) rep(j, 0, 2) scanf("%d", &a[i][j]);
rep(i, 1, n) rep(j, 0, 2) scanf("%d", &b[i][j]);
int j=1; modify(1, 1);
rep(i, 1, n)
{
while(j<=n && suma==sumb)
j++, modify(j, 1);
modify(j, -1), j--;
rp[i]=j; modify(i, -1);
}
while(T--)
{
int l, r; scanf("%d%d", &l, &r);
puts(rp[l]>=r?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 10044kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9868kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 10052kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 10052kb
Pretest #5:
score: 5
Accepted
time: 3ms
memory: 12044kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 10052kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9856kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 9944kb
Pretest #9:
score: 5
Accepted
time: 14ms
memory: 9856kb
Pretest #10:
score: 5
Accepted
time: 17ms
memory: 10000kb
Pretest #11:
score: 5
Accepted
time: 78ms
memory: 11740kb
Pretest #12:
score: 5
Accepted
time: 80ms
memory: 12184kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 9868kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 9960kb
Pretest #15:
score: 5
Accepted
time: 106ms
memory: 9868kb
Pretest #16:
score: 5
Accepted
time: 99ms
memory: 10092kb
Pretest #17:
score: 5
Accepted
time: 4ms
memory: 9864kb
Pretest #18:
score: 5
Accepted
time: 3ms
memory: 10984kb
Pretest #19:
score: 5
Accepted
time: 176ms
memory: 11100kb
Pretest #20:
score: 5
Accepted
time: 205ms
memory: 20176kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9908kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9988kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 9868kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 9940kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 9924kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 9912kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 10056kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 10060kb
Test #9:
score: 5
Accepted
time: 18ms
memory: 9868kb
Test #10:
score: 5
Accepted
time: 13ms
memory: 9920kb
Test #11:
score: 5
Accepted
time: 85ms
memory: 12956kb
Test #12:
score: 5
Accepted
time: 90ms
memory: 11184kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 9908kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 10076kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 10000kb
Test #16:
score: 5
Accepted
time: 105ms
memory: 9944kb
Test #17:
score: 5
Accepted
time: 9ms
memory: 9876kb
Test #18:
score: 5
Accepted
time: 0ms
memory: 10936kb
Test #19:
score: 5
Accepted
time: 196ms
memory: 11268kb
Test #20:
score: 5
Accepted
time: 202ms
memory: 20168kb
Extra Test:
score: 0
Extra Test Passed