QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487936 | #9155. 集合 | 275307894a | 100 ✓ | 198ms | 25808kb | C++14 | 1.8kb | 2024-07-23 13:34:56 | 2024-07-23 13:35:00 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;using pii=pair<int,int>;
const int N=6e5+5,M=N*100+5,K=1e7+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=5e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,m,q,A[N][3],B[N][3];
ull w[N];
struct Ha{
ull f[N],sum;
void insert(int x,int y){
sum-=f[x];
f[x]^=w[y];
sum+=f[x];
}
}a,b;
int ans[N];
void Solve(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) for(int j:{0,1,2}) scanf("%d",&A[i][j]);
for(int i=1;i<=n;i++) for(int j:{0,1,2}) scanf("%d",&B[i][j]);
mt19937_64 rnd(time(0));
for(int i=1;i<=n;i++) w[i]=rnd();
int R=1;
for(int i=1;i<=n;i++){
for(int j:{0,1,2}) a.insert(A[i][j],i);
for(int j:{0,1,2}) b.insert(B[i][j],i);
while(a.sum^b.sum){
for(int j:{0,1,2}) a.insert(A[R][j],R);
for(int j:{0,1,2}) b.insert(B[R][j],R);
R++;
}
ans[i]=R;
}
while(q--){
int x,y;scanf("%d%d",&x,&y);
puts(ans[y]<=x?"Yes":"No");
}
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9948kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 10124kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 10124kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 10168kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9948kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 10092kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 10108kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 10104kb
Pretest #9:
score: 5
Accepted
time: 8ms
memory: 10096kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 10072kb
Pretest #11:
score: 5
Accepted
time: 75ms
memory: 17020kb
Pretest #12:
score: 5
Accepted
time: 75ms
memory: 19044kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 10164kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 10200kb
Pretest #15:
score: 5
Accepted
time: 106ms
memory: 10172kb
Pretest #16:
score: 5
Accepted
time: 102ms
memory: 12228kb
Pretest #17:
score: 5
Accepted
time: 5ms
memory: 10148kb
Pretest #18:
score: 5
Accepted
time: 6ms
memory: 11116kb
Pretest #19:
score: 5
Accepted
time: 184ms
memory: 14856kb
Pretest #20:
score: 5
Accepted
time: 198ms
memory: 25808kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 10072kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 10100kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 10108kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10104kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 10164kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10168kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 10148kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 10160kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 10124kb
Test #10:
score: 5
Accepted
time: 17ms
memory: 10160kb
Test #11:
score: 5
Accepted
time: 80ms
memory: 20440kb
Test #12:
score: 5
Accepted
time: 79ms
memory: 16868kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 10108kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 10200kb
Test #15:
score: 5
Accepted
time: 109ms
memory: 10100kb
Test #16:
score: 5
Accepted
time: 103ms
memory: 10184kb
Test #17:
score: 5
Accepted
time: 8ms
memory: 12220kb
Test #18:
score: 5
Accepted
time: 4ms
memory: 11088kb
Test #19:
score: 5
Accepted
time: 184ms
memory: 17112kb
Test #20:
score: 5
Accepted
time: 185ms
memory: 24652kb
Extra Test:
score: 0
Extra Test Passed