QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506774#9155. 集合12345678hzx100 ✓54ms25740kbC++145.1kb2024-08-05 21:35:172024-08-05 21:35:17

Judging History

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

  • [2024-08-05 21:35:17]
  • 评测
  • 测评结果:100
  • 用时:54ms
  • 内存:25740kb
  • [2024-08-05 21:35:17]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<ctime>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>

using namespace std;

class fastIO{private:char ibuf[50007],*p1=ibuf,*p2=ibuf,obuf[50007],*p3=obuf,sta[50];bool file_end=false;char get(){return p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,50007,stdin),p1==p2)?(file_end=true),char(EOF):*p1++;}void put(const char x){p3-obuf<50007?*p3++=x:(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x);}public:explicit operator bool(){return!file_end;}size_t flush(){size_t f=fwrite(obuf,p3-obuf,1,stdout);p3=obuf;*p3=0;return f;}fastIO&operator>>(char&t){for(t=get();!isgraph(t);t=get());return*this;}template<typename any>typename std::enable_if<std::is_same<any,char>::value,any>::type tpval(){char t;for(t=get();!isgraph(t);t=get());return t;}fastIO&operator>>(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}fastIO&operator>>(std::string&t){t.clear();char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return*this;}template<typename any>typename std::enable_if<std::is_same<any,std::string>::value,any>::type tpval(){std::string t;char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return t;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator>>(any&t){t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,any>::type tpval(){any t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return t;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator>>(any&t){t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,any>::type tpval(){any t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return t;}template<typename any1,typename any2>fastIO&operator>>(std::pair<any1,any2>&t){return*this>>t.first>>t.second;}template<typename any1,typename any2>std::pair<any1,any2>tpval(){return std::pair<any1,any2>(tpval<any1>(),tpval<any2>());}template<typename any>fastIO&read(any&t){return*this>>t;}fastIO&read(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}template<typename any,typename...args>fastIO&read(any&t1,args&...t2){return(*this>>t1).read(t2...);}fastIO&operator<<(const char t){put(t);return*this;}fastIO&operator<<(const char*t){for(;*t;t++)put(*t);return*this;}fastIO&operator<<(const std::string&t){for(const char it:t)put(it);return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;if(t<0)t=-t,put(45);while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any1,typename any2>fastIO&operator<<(const std::pair<any1,any2>&t){return*this<<t.first<<' '<<t.second;}template<typename any>fastIO&write(const any&t){return*this<<t;}template<typename any,typename...args>fastIO&write(const any&t1,const args&...t2){return(*this<<t1).write(t2...);}~fastIO(){fwrite(obuf,p3-obuf,1,stdout);}}fio;
long long n,m,M,a[600005],b[600005],R,maxn[200005],H[200005],pos[600005],Pos[600005]; 
__int128 sum,Sum;
unsigned long long Rand(unsigned long long x) {
    if(!x) return x;
    x^=M,x^=x<<7,x^=x>>11,x^=x<<13;
    return x;
}
void update(int x,int op) {
	for(int i=2;i>=0;i--) {
		sum-=Rand(pos[a[x*3-i]]),Sum-=Rand(Pos[b[x*3-i]]);
		pos[a[x*3-i]]+=op*H[x],Pos[b[x*3-i]]+=op*H[x];
		sum+=Rand(pos[a[x*3-i]]),Sum+=Rand(Pos[b[x*3-i]]);
	}
}
int main() {
	srand(time(0));
	fio>>n>>m>>m,M=rand();
	for(int i=1;i<=n;i++) H[i]=rand()*1ll*rand(),fio>>a[i*3-2]>>a[i*3-1]>>a[i*3];
	for(int i=1;i<=n;i++) fio>>b[i*3-2]>>b[i*3-1]>>b[i*3];
	for(int i=1;i<=n;i++) {
		while(R<=n&&sum==Sum) {
			R++;
			if(R<=n) update(R,1);
		}
		maxn[i]=R-1,update(i,-1);
	}
	while(m--) {
		int l,r;
		fio>>l>>r;
		if(maxn[l]>=r) fio<<"Yes\n";
		else fio<<"No\n";
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 19ms
memory: 16804kb

Pretest #12:

score: 5
Accepted
time: 25ms
memory: 17600kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 5ms
memory: 13016kb

Pretest #19:

score: 5
Accepted
time: 46ms
memory: 16508kb

Pretest #20:

score: 5
Accepted
time: 52ms
memory: 25736kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 25ms
memory: 17872kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 25ms
memory: 12144kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 53ms
memory: 16508kb

Test #20:

score: 5
Accepted
time: 54ms
memory: 25740kb

Extra Test:

score: 0
Extra Test Passed