QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716041#9155. 集合KiharaTouma100 ✓541ms61208kbC++142.4kb2024-11-06 14:09:392024-11-06 14:09:39

Judging History

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

  • [2024-11-06 14:09:39]
  • 评测
  • 测评结果:100
  • 用时:541ms
  • 内存:61208kb
  • [2024-11-06 14:09:39]
  • 提交

answer

//qoj9155
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, M = 6e5 + 10;
int n, m, q, a[N][3], b[N][3], rm[N];
typedef unsigned long long ll;
const ll P = 998244853, R = 337;
ll p[N], vx[M], vy[M];
int cnt;
unordered_map<ll, int> mp;

void add(int x){
	for(int i = 0; i <= 2; ++ i){
		if(mp[vx[a[x][i]]] == 0){
			-- cnt;
		} 
		-- mp[vx[a[x][i]]];
		if(mp[vx[a[x][i]]] == 0){
			++ cnt;
		} 
		vx[a[x][i]] = (vx[a[x][i]] + p[x]) % P;
		if(mp[vx[a[x][i]]] == 0){
			-- cnt;
		} 
		++ mp[vx[a[x][i]]];
		if(mp[vx[a[x][i]]] == 0){
			++ cnt;
		}
		if(mp[vy[b[x][i]]] == 0){
			-- cnt;
		} 
		++ mp[vy[b[x][i]]];
		if(mp[vy[b[x][i]]] == 0){
			++ cnt;
		} 
		vy[b[x][i]] = (vy[b[x][i]] + p[x]) % P;
		if(mp[vy[b[x][i]]] == 0){
			-- cnt;
		} 
		-- mp[vy[b[x][i]]];
		if(mp[vy[b[x][i]]] == 0){
			++ cnt;
		} 
	}
}

void del(int x){
	for(int i = 0; i <= 2; ++ i){
//		printf("-1- %lld %d\n", vx[a[x][i]], mp[vx[a[x][i]]]);
		if(mp[vx[a[x][i]]] == 0){
			-- cnt;
		} 
		-- mp[vx[a[x][i]]];
		if(mp[vx[a[x][i]]] == 0){
			++ cnt;
		} 
		vx[a[x][i]] = (vx[a[x][i]] + P - p[x]) % P;
		if(mp[vx[a[x][i]]] == 0){
			-- cnt;
		} 
		++ mp[vx[a[x][i]]];
		if(mp[vx[a[x][i]]] == 0){
			++ cnt;
		}
//		printf("-2- %lld %d\n", vx[a[x][i]], mp[vx[a[x][i]]]);
//		printf("-3- %lld %d\n", vy[b[x][i]], mp[vy[b[x][i]]]);
		if(mp[vy[b[x][i]]] == 0){
			-- cnt;
		} 
		++ mp[vy[b[x][i]]];
		if(mp[vy[b[x][i]]] == 0){
			++ cnt;
		} 
		vy[b[x][i]] = (vy[b[x][i]] + P - p[x]) % P;
		if(mp[vy[b[x][i]]] == 0){
			-- cnt;
		} 
		-- mp[vy[b[x][i]]];
		if(mp[vy[b[x][i]]] == 0){
			++ cnt;
		} 
//		printf("-4- %lld %d\n", vy[b[x][i]], mp[vy[b[x][i]]]);
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	p[0] = 1;
	for(int i = 1; i <= n; ++ i){
		for(int j = 0; j < 3; ++ j){
			scanf("%d", &a[i][j]);
		}
		p[i] = p[i-1] * R % P;
	}
	for(int i = 1; i <= n; ++ i){
		for(int j = 0; j < 3; ++ j){
			scanf("%d", &b[i][j]);
		}
	}
	cnt = m;
	for(int l = 1, r = 0; l <= n; ++ l){
		while(r < n){
			++ r;
			add(r);
//			printf("%d %d %d\n%llu %llu %llu %llu\n", l, r, cnt, vx[1],vx[2],vx[3],vx[4]);
//			printf("%llu %llu %llu %llu\n", vy[1],vy[2],vy[3],vy[4]);
			if(cnt != m){
				del(r);
				-- r;
				break;
			}
		}
		rm[l] = r;
		del(l);
	}
	while(q--){
		int l, r;
		scanf("%d%d", &l, &r);
		if(rm[l] >= r){
			puts("Yes");
		} else {
			puts("No");
		}
	}
	return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 9736kb

Pretest #2:

score: 5
Accepted
time: 1ms
memory: 10092kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 9796kb

Pretest #4:

score: 5
Accepted
time: 1ms
memory: 11872kb

Pretest #5:

score: 5
Accepted
time: 1ms
memory: 9752kb

Pretest #6:

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

Pretest #7:

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

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 10084kb

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 18ms
memory: 9856kb

Pretest #11:

score: 5
Accepted
time: 459ms
memory: 61208kb

Pretest #12:

score: 5
Accepted
time: 409ms
memory: 57352kb

Pretest #13:

score: 5
Accepted
time: 2ms
memory: 12520kb

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 112ms
memory: 10216kb

Pretest #16:

score: 5
Accepted
time: 116ms
memory: 12576kb

Pretest #17:

score: 5
Accepted
time: 30ms
memory: 16360kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 508ms
memory: 55828kb

Pretest #20:

score: 5
Accepted
time: 529ms
memory: 60188kb

Final Tests

Test #1:

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

Test #2:

score: 5
Accepted
time: 2ms
memory: 12144kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 11856kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 9816kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9828kb

Test #6:

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

Test #7:

score: 5
Accepted
time: 1ms
memory: 9856kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 9788kb

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 411ms
memory: 58156kb

Test #12:

score: 5
Accepted
time: 395ms
memory: 54968kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 5ms
memory: 12292kb

Test #15:

score: 5
Accepted
time: 101ms
memory: 10188kb

Test #16:

score: 5
Accepted
time: 120ms
memory: 10288kb

Test #17:

score: 5
Accepted
time: 30ms
memory: 16280kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 496ms
memory: 55972kb

Test #20:

score: 5
Accepted
time: 541ms
memory: 60832kb

Extra Test:

score: 0
Extra Test Passed