QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507289#9155. 集合juruoA100 ✓108ms34920kbC++142.4kb2024-08-06 15:22:352024-08-06 15:22:36

Judging History

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

  • [2024-08-06 15:22:36]
  • 评测
  • 测评结果:100
  • 用时:108ms
  • 内存:34920kb
  • [2024-08-06 15:22:35]
  • 提交

answer

#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;
		
inline li read(){
	li ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 
		
li n, m, q;
const li base = 114251;
li R[200010];
		
li G(li x){
	return 191981 * x * x * x * x - 114514 * x * x * x - 363415 * x * x + 251251 * x - 2333333;
}
li now[600010][2], a[200010][5][2], poww[600010], ans[2];
std::mt19937_64 rng(251);
		
int main(){
//	 freopen("wonderful.ans", "r", stdin);
//	 freopen("www.ww", "w", stdout); 
	n = read(), m = read(), q = read();
	poww[0] = 1;
	for(li i = 1; i <= 6e5; i++) poww[i] = rng();
	for(li i = 1; i <= n; i++){
		a[i][1][0] = read(), a[i][2][0] = read(), a[i][3][0] = read();
	}
	for(li i = 1; i <= n; i++){
		a[i][1][1] = read(), a[i][2][1] = read(), a[i][3][1] = read();
	}
	li r = 0;
	for(li l = 1; l <= n; l++){
		while(r <= n && ans[1] == ans[0]){
//			cout << l << " " << r << endl;
			r++;
			for(li i = 0; i < 2; i++){
				for(li j = 1; j <= 3; j++){
//					printf("ans %lld -= G(%lld)\n", i, now[a[r][j][i]][i]);
					ans[i] -= G(now[a[r][j][i]][i]);
					now[a[r][j][i]][i] += poww[r];
//					printf("ans %lld += G(%lld)\n", i, now[a[r][j][i]][i]);
					ans[i] += G(now[a[r][j][i]][i]);
				}
			}
		}
		for(li i = 0; i < 2; i++){
			for(li j = 1; j <= 3; j++){
//				printf("ans %lld -= G(%lld)\n", i, now[a[l][j][i]][i]);
				ans[i] -= G(now[a[l][j][i]][i]);
				now[a[l][j][i]][i] -= poww[l];
//				printf("ans %lld += G(%lld)\n", i, now[a[l][j][i]][i]);
				ans[i] += G(now[a[l][j][i]][i]);
			}
		}
		R[l] = r - 1;
		if(R[l] < l) r = l - 1, ans[0] = ans[1] = 0;
//		printf("r %lld = %lld\n", l, R[l]);
	}
	while(q--){
		li x = read(), y = read();
		if(R[x] >= y) puts("Yes");
		else puts("No");
	}
	return 0;
} 

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 11ms
memory: 10860kb

Pretest #10:

score: 5
Accepted
time: 11ms
memory: 11016kb

Pretest #11:

score: 5
Accepted
time: 26ms
memory: 28712kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 53ms
memory: 8844kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 91ms
memory: 26684kb

Pretest #20:

score: 5
Accepted
time: 107ms
memory: 34920kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 11ms
memory: 11052kb

Test #10:

score: 5
Accepted
time: 11ms
memory: 8376kb

Test #11:

score: 5
Accepted
time: 37ms
memory: 28648kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 41ms
memory: 11288kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 85ms
memory: 28732kb

Test #20:

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

Extra Test:

score: 0
Extra Test Passed