QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488654 | #9155. 集合 | IvanZhang2009 | 100 ✓ | 409ms | 68576kb | C++14 | 3.9kb | 2024-07-24 12:58:13 | 2024-07-24 12:58:13 |
Judging History
answer
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* 神兽保佑 永无BUG
*/
/*
* @Description: I want to be the weakest vegetable in the world!
* @Author: I.Z.
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define speMOD 2933256077ll
#define int long long
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define pb push_back
#define REP(i,b,e) for(int i=(b);i<(int)(e);++i)
#define over(x) {cout<<(x)<<endl;return;}
#define lowbit(x) ((x)&(-(x)))
#define cntbit(x) __builtin_popcount(x)
#define rf(v) shuffle(all(v),sd);
#define deal(v) sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
mt19937 sd(random_device{}());
int qpow(int a,int b,int m=MOD,int res=1){
a%=m;
while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
return res;
}
string YN(bool x,string Y="Yes",string N="No") {
if(x){
return Y;
} else {
return N;
}
}
int exgcd(int x,int y,int &a,int &b){
if(y==0){
a=1;b=0;
return x;
}
int d=exgcd(y,x%y,a,b);
int z=b;
b=a-b*(x/y);
a=z;
return d;
}
int _x_,_y_;
inline int inverse(int x,int y=MOD){
exgcd(x,y,_x_,_y_);
return (_x_+y)%y;
}
int fac[2000005],inv[2000005];
void init(int n){
fac[0]=inv[0]=1;
REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
inv[n]=qpow(fac[n],MOD-2);
for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int binom(int x,int y){
return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
#define ull unsigned int
int n,m,q;
vector<int>a[600005],b[600005];
uniform_int_distribution<int>rd(0,(1ll<<32)-1);
ull val[600005];
ull c1[600005],c2[600005];
ull vala,valb,v2a,v2b;
void add(int i){
for(auto j:a[i]){
vala-=c1[j];v2a-=c1[j]*c1[j];
c1[j]^=val[i];
vala+=c1[j];v2a+=c1[j]*c1[j];
}
for(auto j:b[i]){
valb-=c2[j];v2b-=c2[j]*c2[j];
c2[j]^=val[i];
valb+=c2[j];v2b+=c2[j]*c2[j];
}
}
int rt[600005];
void Main() {
cin>>n>>m>>q;
REP(i,0,n){
REP(j,0,3){
int x;
cin>>x;--x;
a[i].pb(x);
}
}
REP(i,0,n){
REP(j,0,3){
int x;
cin>>x;--x;
b[i].pb(x);
}
}
REP(i,0,n)val[i]=(rd(sd)<<32)|rd(sd);
int x=-1;
REP(i,0,n){
while(x+1<n&&vala==valb&&v2a==v2b)add(++x);
if(vala!=valb||v2a!=v2b)add(x--);
rt[i]=x;
add(i);
}
while(q--){
int x,y;
cin>>x>>y;
cout<<(rt[x-1]>=y-1? "Yes":"No")<<endl;
}
}
void TC() {
int tc=1;
while(tc--){
Main();
cout.flush();
}
}
signed main() {
return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 8ms
memory: 34492kb
Pretest #2:
score: 5
Accepted
time: 3ms
memory: 36404kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 34340kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 36320kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 36272kb
Pretest #6:
score: 5
Accepted
time: 4ms
memory: 36404kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 34244kb
Pretest #8:
score: 5
Accepted
time: 3ms
memory: 36404kb
Pretest #9:
score: 5
Accepted
time: 47ms
memory: 36292kb
Pretest #10:
score: 5
Accepted
time: 56ms
memory: 36360kb
Pretest #11:
score: 5
Accepted
time: 111ms
memory: 57448kb
Pretest #12:
score: 5
Accepted
time: 112ms
memory: 59756kb
Pretest #13:
score: 5
Accepted
time: 7ms
memory: 36536kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 36680kb
Pretest #15:
score: 5
Accepted
time: 228ms
memory: 34728kb
Pretest #16:
score: 5
Accepted
time: 319ms
memory: 36848kb
Pretest #17:
score: 5
Accepted
time: 12ms
memory: 36364kb
Pretest #18:
score: 5
Accepted
time: 13ms
memory: 37524kb
Pretest #19:
score: 5
Accepted
time: 391ms
memory: 60008kb
Pretest #20:
score: 5
Accepted
time: 409ms
memory: 65856kb
Final Tests
Test #1:
score: 5
Accepted
time: 4ms
memory: 34524kb
Test #2:
score: 5
Accepted
time: 4ms
memory: 36400kb
Test #3:
score: 5
Accepted
time: 3ms
memory: 34268kb
Test #4:
score: 5
Accepted
time: 3ms
memory: 36612kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 36384kb
Test #6:
score: 5
Accepted
time: 3ms
memory: 36316kb
Test #7:
score: 5
Accepted
time: 4ms
memory: 36336kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 36356kb
Test #9:
score: 5
Accepted
time: 47ms
memory: 34284kb
Test #10:
score: 5
Accepted
time: 68ms
memory: 34356kb
Test #11:
score: 5
Accepted
time: 151ms
memory: 59740kb
Test #12:
score: 5
Accepted
time: 128ms
memory: 56688kb
Test #13:
score: 5
Accepted
time: 7ms
memory: 36524kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 36916kb
Test #15:
score: 5
Accepted
time: 244ms
memory: 36592kb
Test #16:
score: 5
Accepted
time: 335ms
memory: 34860kb
Test #17:
score: 5
Accepted
time: 17ms
memory: 38412kb
Test #18:
score: 5
Accepted
time: 17ms
memory: 39284kb
Test #19:
score: 5
Accepted
time: 371ms
memory: 56608kb
Test #20:
score: 5
Accepted
time: 356ms
memory: 68576kb
Extra Test:
score: 0
Extra Test Passed