QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488654#9155. 集合IvanZhang2009100 ✓409ms68576kbC++143.9kb2024-07-24 12:58:132024-07-24 12:58:13

Judging History

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

  • [2024-07-24 12:58:13]
  • 评测
  • 测评结果:100
  • 用时:409ms
  • 内存:68576kb
  • [2024-07-24 12:58:13]
  • 提交

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