QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497672 | #9155. 集合 | Clonoth | 100 ✓ | 66ms | 28292kb | C++17 | 1.8kb | 2024-07-29 15:44:45 | 2024-07-29 15:44:46 |
Judging History
answer
#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
template<typename type>
inline void chmin(type &x,const type &y)
{
if(y<x)
x=y;
}
template<typename type>
inline void chmax(type &x,const type &y)
{
if(x<y)
x=y;
}
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x)
{
x=0;
bool f=false;
char ch=getchar();
while(ch<'0'||ch>'9')
f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')
x=x*10+(ch^48),ch=getchar();
if(f)
x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y)
{
read(x),read(y...);
}
constexpr int Max=2e5+10,Size=Max*3;
mt19937_64 rng(666);
ull num[Max];
int n,m,q;
int a[Max][3],b[Max][3],val[Max];
struct shengqile
{
ull f[Size],ans;
inline void add(int x,int y)// a[x] = y
{
ans-=f[y]*f[y];
f[y]^=num[x];
ans+=f[y]*f[y];
}
}A,B;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
read(n,m,q);
for(int i=1;i<=n;++i)
num[i]=rng();
for(int i=1;i<=n;++i)
read(a[i][0],a[i][1],a[i][2]);
for(int i=1;i<=n;++i)
read(b[i][0],b[i][1],b[i][2]);
for(int i=1,j=0;i<=n;++i)
{
val[i]=val[i-1];
while(A.ans==B.ans)
{
val[i]=j;
if(j==n)
break;
++j;
for(int x:a[j])
A.add(j,x);
for(int x:b[j])
B.add(j,x);
}
for(int x:a[i])
A.add(i,x);
for(int x:b[i])
B.add(i,x);
}
int l,r;
while(q--)
{
read(l,r);
if(val[l]>=r)
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9768kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11820kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 11792kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 11816kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 9856kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 11888kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 11816kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 11756kb
Pretest #9:
score: 5
Accepted
time: 8ms
memory: 11824kb
Pretest #10:
score: 5
Accepted
time: 9ms
memory: 13804kb
Pretest #11:
score: 5
Accepted
time: 15ms
memory: 17968kb
Pretest #12:
score: 5
Accepted
time: 18ms
memory: 17996kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 11776kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 11992kb
Pretest #15:
score: 5
Accepted
time: 34ms
memory: 17768kb
Pretest #16:
score: 5
Accepted
time: 39ms
memory: 18972kb
Pretest #17:
score: 5
Accepted
time: 3ms
memory: 13808kb
Pretest #18:
score: 5
Accepted
time: 0ms
memory: 14800kb
Pretest #19:
score: 5
Accepted
time: 53ms
memory: 18888kb
Pretest #20:
score: 5
Accepted
time: 66ms
memory: 28276kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 11844kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 11912kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 11784kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 11808kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9728kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 11900kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 11900kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 11908kb
Test #9:
score: 5
Accepted
time: 4ms
memory: 13944kb
Test #10:
score: 5
Accepted
time: 3ms
memory: 11884kb
Test #11:
score: 5
Accepted
time: 16ms
memory: 17996kb
Test #12:
score: 5
Accepted
time: 15ms
memory: 15876kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 11820kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 9904kb
Test #15:
score: 5
Accepted
time: 38ms
memory: 18552kb
Test #16:
score: 5
Accepted
time: 34ms
memory: 18428kb
Test #17:
score: 5
Accepted
time: 0ms
memory: 13880kb
Test #18:
score: 5
Accepted
time: 0ms
memory: 12828kb
Test #19:
score: 5
Accepted
time: 48ms
memory: 20000kb
Test #20:
score: 5
Accepted
time: 63ms
memory: 28292kb
Extra Test:
score: 0
Extra Test Passed