QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497543 | #9155. 集合 | Kalenist | 100 ✓ | 717ms | 90192kb | C++14 | 2.2kb | 2024-07-29 13:22:06 | 2024-07-29 13:22:07 |
Judging History
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