QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490132#9155. 集合staring#100 ✓200ms20332kbC++232.3kb2024-07-25 11:40:052024-07-25 11:40:05

Judging History

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

  • [2024-07-25 11:40:05]
  • 评测
  • 测评结果:100
  • 用时:200ms
  • 内存:20332kb
  • [2024-07-25 11:40:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
constexpr int N=2e5+5,M=6e5+5;
constexpr int MOD1=1e9+7,MOD2=1e9+9;

int a[N][3],b[N][3];
int ahash1[M],ahash2[M];
int bhash1[M],bhash2[M];
int pow1[N],pow2[N];
int rightp[N];

void mod1(int& a,int b){a+=b,a>=MOD1?a-=MOD1:0;}
void mod2(int& a,int b){a+=b,a>=MOD2?a-=MOD2:0;}

void add(int i)
{
    mod1(ahash1[a[i][0]],pow1[i]),mod1(ahash1[a[i][1]],pow1[i]),mod1(ahash1[a[i][2]],pow1[i]);
    mod2(ahash2[a[i][0]],pow2[i]),mod2(ahash2[a[i][1]],pow2[i]),mod2(ahash2[a[i][2]],pow2[i]);

    mod1(bhash1[b[i][0]],pow1[i]),mod1(bhash1[b[i][1]],pow1[i]),mod1(bhash1[b[i][2]],pow1[i]);
    mod2(bhash2[b[i][0]],pow2[i]),mod2(bhash2[b[i][1]],pow2[i]),mod2(bhash2[b[i][2]],pow2[i]);
}

void del(int i)
{
    mod1(ahash1[a[i][0]],MOD1-pow1[i]),mod1(ahash1[a[i][1]],MOD1-pow1[i]),mod1(ahash1[a[i][2]],MOD1-pow1[i]);
    mod2(ahash2[a[i][0]],MOD2-pow2[i]),mod2(ahash2[a[i][1]],MOD2-pow2[i]),mod2(ahash2[a[i][2]],MOD2-pow2[i]);

    mod1(bhash1[b[i][0]],MOD1-pow1[i]),mod1(bhash1[b[i][1]],MOD1-pow1[i]),mod1(bhash1[b[i][2]],MOD1-pow1[i]);
    mod2(bhash2[b[i][0]],MOD2-pow2[i]),mod2(bhash2[b[i][1]],MOD2-pow2[i]),mod2(bhash2[b[i][2]],MOD2-pow2[i]);
}

int check(int i)
{
    vector<PII> va{{ahash1[a[i][0]],ahash2[a[i][0]]},{ahash1[a[i][1]],ahash2[a[i][1]]},{ahash1[a[i][2]],ahash2[a[i][2]]}};
    vector<PII> vb{{bhash1[b[i][0]],bhash2[b[i][0]]},{bhash1[b[i][1]],bhash2[b[i][1]]},{bhash1[b[i][2]],bhash2[b[i][2]]}};
    sort(va.begin(),va.end()),sort(vb.begin(),vb.end());
    return va[0]==vb[0]&&va[1]==vb[1]&&va[2]==vb[2];
}

int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);

    pow1[0]=pow2[0]=1;
    for(int i=1;i<=n;i++)pow1[i]=pow1[i-1]<<1,pow1[i]>=MOD1?pow1[i]-=MOD1:0,pow2[i]=pow2[i-1]<<1,pow2[i]>=MOD2?pow2[i]-=MOD2:0;
    for(int i=1,j=0;i<=n;i++)
    {
        do add(++j);while(j<=n&&check(j));
        del(i),del(j),rightp[i]=--j;
    }
    for(int i=1;i<=n;i++)rightp[i]=max(rightp[i],rightp[i-1]);

    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        puts(rightp[l]>=r?"Yes":"No");
    }

    return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 7780kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 10056kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 10056kb

Pretest #4:

score: 5
Accepted
time: 1ms
memory: 9860kb

Pretest #5:

score: 5
Accepted
time: 1ms
memory: 9800kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 7824kb

Pretest #7:

score: 5
Accepted
time: 1ms
memory: 9828kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 7828kb

Pretest #9:

score: 5
Accepted
time: 16ms
memory: 9824kb

Pretest #10:

score: 5
Accepted
time: 21ms
memory: 10088kb

Pretest #11:

score: 5
Accepted
time: 86ms
memory: 12168kb

Pretest #12:

score: 5
Accepted
time: 90ms
memory: 11932kb

Pretest #13:

score: 5
Accepted
time: 2ms
memory: 10092kb

Pretest #14:

score: 5
Accepted
time: 2ms
memory: 7880kb

Pretest #15:

score: 5
Accepted
time: 101ms
memory: 9824kb

Pretest #16:

score: 5
Accepted
time: 106ms
memory: 10172kb

Pretest #17:

score: 5
Accepted
time: 4ms
memory: 12016kb

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 10680kb

Pretest #19:

score: 5
Accepted
time: 200ms
memory: 12148kb

Pretest #20:

score: 5
Accepted
time: 199ms
memory: 20068kb

Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 10056kb

Test #2:

score: 5
Accepted
time: 1ms
memory: 9828kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 9756kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 9760kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9828kb

Test #6:

score: 5
Accepted
time: 1ms
memory: 9800kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 9824kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 7768kb

Test #9:

score: 5
Accepted
time: 20ms
memory: 9824kb

Test #10:

score: 5
Accepted
time: 16ms
memory: 9824kb

Test #11:

score: 5
Accepted
time: 83ms
memory: 12120kb

Test #12:

score: 5
Accepted
time: 87ms
memory: 11860kb

Test #13:

score: 5
Accepted
time: 2ms
memory: 8040kb

Test #14:

score: 5
Accepted
time: 2ms
memory: 9948kb

Test #15:

score: 5
Accepted
time: 95ms
memory: 10116kb

Test #16:

score: 5
Accepted
time: 107ms
memory: 10172kb

Test #17:

score: 5
Accepted
time: 4ms
memory: 9888kb

Test #18:

score: 5
Accepted
time: 9ms
memory: 10584kb

Test #19:

score: 5
Accepted
time: 194ms
memory: 14000kb

Test #20:

score: 5
Accepted
time: 188ms
memory: 20332kb

Extra Test:

score: 0
Extra Test Passed