QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716060#9155. 集合KiharaTouma100 ✓533ms60700kbC++142.1kb2024-11-06 14:12:502024-11-06 14:12:51

Judging History

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

  • [2024-11-06 14:12:51]
  • 评测
  • 测评结果:100
  • 用时:533ms
  • 内存:60700kb
  • [2024-11-06 14:12:50]
  • 提交

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){
		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;
		}
		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;
		} 
	}
}

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);
			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: 9832kb

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 23ms
memory: 9864kb

Pretest #11:

score: 5
Accepted
time: 410ms
memory: 60536kb

Pretest #12:

score: 5
Accepted
time: 390ms
memory: 57740kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 109ms
memory: 10140kb

Pretest #16:

score: 5
Accepted
time: 118ms
memory: 10564kb

Pretest #17:

score: 5
Accepted
time: 29ms
memory: 14284kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 517ms
memory: 56108kb

Pretest #20:

score: 5
Accepted
time: 519ms
memory: 60376kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 420ms
memory: 58828kb

Test #12:

score: 5
Accepted
time: 380ms
memory: 54532kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

score: 5
Accepted
time: 23ms
memory: 15060kb

Test #19:

score: 5
Accepted
time: 489ms
memory: 54964kb

Test #20:

score: 5
Accepted
time: 533ms
memory: 60700kb

Extra Test:

score: 0
Extra Test Passed