QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#506774 | #9155. 集合 | 12345678hzx | 100 ✓ | 54ms | 25740kb | C++14 | 5.1kb | 2024-08-05 21:35:17 | 2024-08-05 21:35:17 |
Judging History
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