QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#606208#9155. 集合Jerrywang100 ✓205ms20176kbC++141.3kb2024-10-02 23:14:112024-10-02 23:14:11

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 23:14:11]
  • 评测
  • 测评结果:100
  • 用时:205ms
  • 内存:20176kb
  • [2024-10-02 23:14:11]
  • 提交

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