QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487453 | #9155. 集合 | TulipeNoire | 100 ✓ | 168ms | 42200kb | C++14 | 2.0kb | 2024-07-22 21:52:00 | 2024-07-22 21:52:00 |
Judging History
answer
#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
using namespace std;
mt19937_64 myrand(time(NULL));
using LL=long long;
using uint=unsigned;
using pii=pair<int,int>;
using vi=vector<int>;
using vp=vector<pii>;
template<typename T>inline void read(T&t){
t=0;
char c=getchar();
int f=1;
while (!isdigit(c)) f=c=='-'?-f:f,c=getchar();
while (isdigit(c)) t=(t<<3)+(t<<1)+c-'0',c=getchar();
t*=f;
return;
}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t),read(args...);}
template<typename T>void write(T x){if(x>=10)write(x/10);putchar(x%10+'0');return;}
template<typename T>inline bool chkmax(T&x,T y){return y>x?(x=y,1):0;}
template<typename T>inline bool chkmin(T&x,T y){return y<x?(x=y,1):0;}
const int N=200005;
int n,m,q,a[N][3],b[N][3],maxr[N];
LL val[N][3],nowa[N*3][3],nowb[N*3][3],suma[3],sumb[3];
inline void update(int x) {
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
suma[j]-=nowa[a[x][i]][j],sumb[j]-=nowb[b[x][i]][j];
nowa[a[x][i]][j]^=val[x][j];
nowb[b[x][i]][j]^=val[x][j];
suma[j]+=nowa[a[x][i]][j],sumb[j]+=nowb[b[x][i]][j];
}
}
}
int main() {
read(n,m,q);
for (int i=1;i<=n;i++) {
for (int j=0;j<3;j++) read(a[i][j]);
for (int j=0;j<3;j++) val[i][j]=myrand()&((1ll<<40)-1);
}
for (int i=1;i<=n;i++) {
for (int j=0;j<3;j++) read(b[i][j]);
}
int r=0;
for (int i=1;i<=n;i++) {
while (1) {
if (r<n) {
update(++r);
if (suma[0]!=sumb[0]||suma[1]!=sumb[1]||suma[2]!=sumb[2]) {
update(r--);
break;
}
} else break;
}
maxr[i]=r;
update(i);
}
while (q--) {
int l,r;
scanf("%d %d",&l,&r);
if (r<=maxr[l]) puts("Yes");
else puts("No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 10040kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 10000kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 10076kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 9852kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 11896kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 11912kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 11992kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 11988kb
Pretest #9:
score: 5
Accepted
time: 22ms
memory: 10044kb
Pretest #10:
score: 5
Accepted
time: 22ms
memory: 11964kb
Pretest #11:
score: 5
Accepted
time: 48ms
memory: 14464kb
Pretest #12:
score: 5
Accepted
time: 41ms
memory: 15464kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 11900kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 12312kb
Pretest #15:
score: 5
Accepted
time: 104ms
memory: 11900kb
Pretest #16:
score: 5
Accepted
time: 115ms
memory: 10224kb
Pretest #17:
score: 5
Accepted
time: 2ms
memory: 12128kb
Pretest #18:
score: 5
Accepted
time: 4ms
memory: 14904kb
Pretest #19:
score: 5
Accepted
time: 154ms
memory: 14908kb
Pretest #20:
score: 5
Accepted
time: 168ms
memory: 42200kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 10052kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 10004kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 9980kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 9920kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 10040kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 12100kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 10000kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 9980kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 10048kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 10072kb
Test #11:
score: 5
Accepted
time: 50ms
memory: 14860kb
Test #12:
score: 5
Accepted
time: 45ms
memory: 13944kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 9940kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 12316kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 11952kb
Test #16:
score: 5
Accepted
time: 113ms
memory: 12340kb
Test #17:
score: 5
Accepted
time: 5ms
memory: 12076kb
Test #18:
score: 5
Accepted
time: 9ms
memory: 14856kb
Test #19:
score: 5
Accepted
time: 138ms
memory: 15748kb
Test #20:
score: 5
Accepted
time: 162ms
memory: 42172kb
Extra Test:
score: 0
Extra Test Passed