QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497543#9155. 集合Kalenist100 ✓717ms90192kbC++142.2kb2024-07-29 13:22:062024-07-29 13:22:07

Judging History

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

  • [2024-07-29 13:22:07]
  • 评测
  • 测评结果:100
  • 用时:717ms
  • 内存:90192kb
  • [2024-07-29 13:22:06]
  • 提交

answer

#include<bits/stdc++.h>
#define N 200010
#define mod0 1000000007
#define mod1 1000000009
#define pii pair<int,int>
#define For(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n,m,q,ans[N*5],val[2][N*3];
int v[2][N*3][2],ha[2][2];
vector<int> a[N*3],b[N*3];
vector<pii> h[N*3];
mt19937_64 rnd(20061130);
inline void add0(int &x,int y){x+=y;if(x>=mod0) x-=mod0;}
inline void add1(int &x,int y){x+=y;if(x>=mod1) x-=mod1;}
inline int read()
{
    register int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

inline void print(bool ans)
{
    if(ans == 1) putchar('Y'),putchar('e'),putchar('s');
    else putchar('N'),putchar('o');
    return void(putchar('\n'));
}

inline int fpow0(int a,int b)
{
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod0)
        if(b&1) res=1ll*res*a%mod0;
    return res;
}

inline int fpow1(int a,int b)
{
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod1)
        if(b&1) res=1ll*res*a%mod1;
    return res;
}

inline void modify(int x,int p,int t,int flag)
{
    ha[t][0]=1ll*ha[t][0]*fpow0(v[t][x][0],mod0-2)%mod0;
    add0(v[t][x][0],flag?val[0][p]:mod0-val[0][p]);
    ha[t][0]=1ll*ha[t][0]*v[t][x][0]%mod0;
    ha[t][1]=1ll*ha[t][1]*fpow1(v[t][x][1],mod1-2)%mod1;
    add1(v[t][x][1],flag?val[1][p]:mod1-val[1][p]);
    ha[t][1]=1ll*ha[t][1]*v[t][x][1]%mod1;
    return;
}

int main()
{
    n=read(),m=read(),q=read();
    ha[0][0]=ha[0][1]=ha[1][0]=ha[1][1]=1;
    For(i,1,m) v[0][i][0]=v[0][i][1]=v[1][i][0]=v[1][i][1]=1;
    For(i,1,n) val[0][i]=rnd()%mod0,val[1][i]=rnd()%mod1;
    For(i,1,n) For(j,0,2) a[i].push_back(read());
    For(i,1,n) For(j,0,2) b[i].push_back(read());
    For(i,1,q) 
    {
        int l=read(),r=read();
        h[r].push_back(pii(l,i));
    }int p=1;
    For(i,1,n)
    {
        for(int x:a[i]) modify(x,i,0,1);
        for(int x:b[i]) modify(x,i,1,1);
        for(;ha[0][0]!=ha[1][0]||ha[0][1]!=ha[1][1];p++)
        {
            for(int x:a[p]) modify(x,p,0,0);
            for(int x:b[p]) modify(x,p,1,0);
        }for(pii x:h[i]) ans[x.second]=(x.first>=p);
    }For(i,1,q) print(ans[i]);
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 7ms
memory: 55380kb

Pretest #4:

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

Pretest #5:

score: 5
Accepted
time: 3ms
memory: 55300kb

Pretest #6:

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

Pretest #7:

score: 5
Accepted
time: 3ms
memory: 55192kb

Pretest #8:

score: 5
Accepted
time: 6ms
memory: 54648kb

Pretest #9:

score: 5
Accepted
time: 14ms
memory: 58308kb

Pretest #10:

score: 5
Accepted
time: 15ms
memory: 56292kb

Pretest #11:

score: 5
Accepted
time: 602ms
memory: 74164kb

Pretest #12:

score: 5
Accepted
time: 606ms
memory: 74032kb

Pretest #13:

score: 5
Accepted
time: 11ms
memory: 54756kb

Pretest #14:

score: 5
Accepted
time: 13ms
memory: 55088kb

Pretest #15:

score: 5
Accepted
time: 55ms
memory: 70704kb

Pretest #16:

score: 5
Accepted
time: 63ms
memory: 68900kb

Pretest #17:

score: 5
Accepted
time: 67ms
memory: 55796kb

Pretest #18:

score: 5
Accepted
time: 60ms
memory: 55780kb

Pretest #19:

score: 5
Accepted
time: 703ms
memory: 86100kb

Pretest #20:

score: 5
Accepted
time: 694ms
memory: 90192kb

Final Tests

Test #1:

score: 5
Accepted
time: 6ms
memory: 54120kb

Test #2:

score: 5
Accepted
time: 3ms
memory: 55408kb

Test #3:

score: 5
Accepted
time: 3ms
memory: 55360kb

Test #4:

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

Test #5:

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

Test #6:

score: 5
Accepted
time: 3ms
memory: 54188kb

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 7ms
memory: 56392kb

Test #10:

score: 5
Accepted
time: 18ms
memory: 57312kb

Test #11:

score: 5
Accepted
time: 613ms
memory: 72436kb

Test #12:

score: 5
Accepted
time: 609ms
memory: 71248kb

Test #13:

score: 5
Accepted
time: 10ms
memory: 54340kb

Test #14:

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

Test #15:

score: 5
Accepted
time: 63ms
memory: 68700kb

Test #16:

score: 5
Accepted
time: 51ms
memory: 69068kb

Test #17:

score: 5
Accepted
time: 64ms
memory: 55892kb

Test #18:

score: 5
Accepted
time: 65ms
memory: 57200kb

Test #19:

score: 5
Accepted
time: 696ms
memory: 86148kb

Test #20:

score: 5
Accepted
time: 717ms
memory: 90188kb

Extra Test:

score: 0
Extra Test Passed