QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#535335#9155. 集合Crysfly100 ✓93ms39612kbC++171.8kb2024-08-27 23:25:362024-08-27 23:25:38

Judging History

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

  • [2024-08-27 23:25:38]
  • 评测
  • 测评结果:100
  • 用时:93ms
  • 内存:39612kb
  • [2024-08-27 23:25:36]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 600006
#define inf 0x3f3f3f3f

int n,m,Q,a[maxn][3],b[maxn][3];
mt19937_64 rnd(time(0));
int tmpa[maxn],tmpb[maxn],nxta[maxn][3],nxtb[maxn][3];

int maxr[maxn];
ull val[maxn];
ull sa[600005],sb[600005];
int per[4];
bool chk(int ii){
	For(i,0,2)per[i]=i;
	do{
		bool ok=1;
		For(i,0,2) ok&=(sa[a[ii][i]]==sb[b[ii][per[i]]]);
		if(ok)return 1;
	}while(next_permutation(per,per+3));
	return 0;
}

signed main()
{
	n=read(),m=read(),Q=read();
	For(i,1,n)val[i]=rnd();
	For(i,1,n)For(j,0,2)a[i][j]=read();
	For(i,1,n)For(j,0,2)b[i][j]=read();
	maxr[n+1]=n;
	Rep(i,n,1){
		For(j,0,2){
			nxta[i][j]=tmpa[a[i][j]],tmpa[a[i][j]]=i;
			nxtb[i][j]=tmpb[b[i][j]],tmpb[b[i][j]]=i;
			sa[a[i][j]]+=val[i];
			sb[b[i][j]]+=val[i];
		}
		maxr[i]=maxr[i+1];
		while(!chk(i)){
			int p=maxr[i]; --maxr[i];
			For(j,0,2){
				sa[a[p][j]]-=val[p];
				sb[b[p][j]]-=val[p];
			}
		}
	}
	For(_,1,Q){
		int l=read(),r=read();
		if(r<=maxr[l])puts("Yes");
		else puts("No");
	}
	return 0;
}
/*

*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 7ms
memory: 18104kb

Pretest #10:

score: 5
Accepted
time: 8ms
memory: 18168kb

Pretest #11:

score: 5
Accepted
time: 22ms
memory: 30440kb

Pretest #12:

score: 5
Accepted
time: 35ms
memory: 26232kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 49ms
memory: 18108kb

Pretest #16:

score: 5
Accepted
time: 50ms
memory: 18196kb

Pretest #17:

score: 5
Accepted
time: 6ms
memory: 19996kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 75ms
memory: 30332kb

Pretest #20:

score: 5
Accepted
time: 93ms
memory: 39612kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 8ms
memory: 18036kb

Test #11:

score: 5
Accepted
time: 24ms
memory: 30264kb

Test #12:

score: 5
Accepted
time: 28ms
memory: 30248kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 44ms
memory: 18156kb

Test #16:

score: 5
Accepted
time: 49ms
memory: 18076kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 7ms
memory: 18956kb

Test #19:

score: 5
Accepted
time: 87ms
memory: 30296kb

Test #20:

score: 5
Accepted
time: 93ms
memory: 39136kb

Extra Test:

score: 0
Extra Test Passed