QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#508244#9155. 集合wangif424100 ✓196ms30604kbC++142.2kb2024-08-07 10:47:272024-08-07 10:47:28

Judging History

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

  • [2024-08-07 10:47:28]
  • 评测
  • 测评结果:100
  • 用时:196ms
  • 内存:30604kb
  • [2024-08-07 10:47:27]
  • 提交

answer

#include <bits/stdc++.h>
#define R(x) x = read()
#define int unsigned long long
#define pii pair<int,int>
#define iax INT_MAX
#define iin INT_MIN
#define lax LLONG_MAX
#define lin LLONG_MIN
#define sqrt sqrtl
bool Mbe;
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c){(pp-pbuf==1<<20)?fwrite(pbuf,1,1<<20,stdout),pp=pbuf,*pp++=c:*pp++=c;}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	x<0&&(push('-'),x=-x);
	static int sta[60]={},top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){ch=='-'&&(f=-1);ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
mt19937_64 rd(time(0));
int n,m,q;
int f[600100];
int c[600100],d[600100];
int hsa,hsb;
int a[200100][3],b[200100][3];
map<int,int> gs,gm;
int tor[200100];
int hsh(int x){
	if(x==0)return x;
	x^=x<<11;x^=x>>4;x^=x<<5;x^=x<<14;
	x+=(++x)+(x++);
	return x;
}
void add(int i,int tp){
	if(tp==1)for(int j=0;j<3;j++){
		int x=a[i][j],y=b[i][j];
		hsa-=hsh(c[x]);hsb-=hsh(d[y]);
		c[x]+=f[i];d[y]+=f[i];
		hsa+=hsh(c[x]);hsb+=hsh(d[y]);
	}else for(int j=0;j<3;j++){
		int x=a[i][j],y=b[i][j];
		hsa-=hsh(c[x]);hsb-=hsh(d[y]);
		c[x]-=f[i];d[y]-=f[i];
		hsa+=hsh(c[x]);hsb+=hsh(d[y]);
	}
}
bool Med;
signed main(){
#ifndef LOCAL
	cerr << (&Med-&Mbe)/1024.0/1024 << "MB\n";
#endif
	R(n);R(m);R(q);
	for(int i=1;i<=n;i++)tor[i]=lax;
	for(int i=1;i<=n;i++)for(int j=0;j<3;j++)R(a[i][j]);
	for(int i=1;i<=n;i++)for(int j=0;j<3;j++)R(b[i][j]);
	for(int T=10;T>=1;T--){
		for(int i=1;i<=n;i++)c[i]=d[i]=0,f[i]=rd();
		hsa=hsb=0;add(1,1);
		for(int l=1,r=1;l<=n;add(l,-1),l++){
			while(r<=n&&hsa==hsb){
				r++;
				add(r,1);
			}
			tor[l]=min(tor[l],r-1);
		}
	}
	while(q--){
		R(int l),R(r);
		if(r<=tor[l])puts("Yes");
		else puts("No");
	}
    return 0;
}
/*
4 4 1
1 2 3 1 2 3 1 2 4 1 2 3
1 2 4 2 3 4 1 2 3 2 3 4
2 3
*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 99ms
memory: 28808kb

Pretest #12:

score: 5
Accepted
time: 108ms
memory: 27856kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 9ms
memory: 18856kb

Pretest #18:

score: 5
Accepted
time: 14ms
memory: 18352kb

Pretest #19:

score: 5
Accepted
time: 142ms
memory: 27968kb

Pretest #20:

score: 5
Accepted
time: 196ms
memory: 30084kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 4ms
memory: 16156kb

Test #10:

score: 5
Accepted
time: 4ms
memory: 18280kb

Test #11:

score: 5
Accepted
time: 105ms
memory: 29288kb

Test #12:

score: 5
Accepted
time: 117ms
memory: 30604kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 4ms
memory: 16256kb

Test #15:

score: 5
Accepted
time: 33ms
memory: 16304kb

Test #16:

score: 5
Accepted
time: 39ms
memory: 18224kb

Test #17:

score: 5
Accepted
time: 13ms
memory: 16316kb

Test #18:

score: 5
Accepted
time: 14ms
memory: 20268kb

Test #19:

score: 5
Accepted
time: 155ms
memory: 27744kb

Test #20:

score: 5
Accepted
time: 175ms
memory: 30304kb

Extra Test:

score: 0
Extra Test Passed