QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693946#9327. Permutation and Querieslytqwq#TL 355ms16388kbC++142.1kb2024-10-31 17:00:122024-10-31 17:00:17

Judging History

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

  • [2024-10-31 17:00:17]
  • 评测
  • 测评结果：TL
  • 用时：355ms
  • 内存：16388kb
查看
  • [2024-10-31 17:00:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,p[N],wz[N];
int L;
long long ans[N]; 
multiset<int> dk[N];
long long ask(){
	long long ans=1e9;
	for(int i=1;i<=L;i++){
		
		int x=(*dk[i].begin());
		ans=min(ans,i*1ll*x);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		wz[p[i]]=i;
	}
	L=sqrt(n);
	for(int i=1;i<=L;i++){
		for(int v=1;v+i<=n;v++){
			dk[i].insert(abs(p[v+i]-p[v]));
			dk[i].insert(abs(wz[v+i]-wz[v]));
		}
	}
	printf("%lld\n",ask());
//	ans[0]=ask();
	for(int i=1;i<=q;i++){
		
		int l,r;
		scanf("%d%d",&l,&r);
		if(l>r)swap(l,r);
		for(int v=1;v<=L;v++){
			if(l+v<=n)
			dk[v].erase(dk[v].find(abs(p[l+v]-p[l])));
			if(r+v<=n)
			dk[v].erase(dk[v].find(abs(p[r+v]-p[r])));
			if(l+v!=r)
			if(r-v>=1)
			dk[v].erase(dk[v].find(abs(p[r-v]-p[r])));
			if(l-v>=1)
			dk[v].erase(dk[v].find(abs(p[l-v]-p[l])));
			
			
			
			if(p[l]+v<=n)
			dk[v].erase(dk[v].find(abs(l-wz[p[l]+v])));
			if(p[l]-v>=1)
			dk[v].erase(dk[v].find(abs(l-wz[p[l]-v])));
			if(p[r]+v!=p[l])
			if(p[r]+v<=n)
			dk[v].erase(dk[v].find(abs(r-wz[p[r]+v])));
			if(p[r]-v!=p[l])
			if(p[r]-v>=1)
			dk[v].erase(dk[v].find(abs(r-wz[p[r]-v])));
			
			
//			if(r+v<=n)
//			dk[v].erase(dk[v].find(abs(p[r+v]-p[r])));
//			if(l+v!=r)
//			if(r-v>=1)
//			dk[v].erase(dk[v].find(abs(p[r-v]-p[r])));
//			if(l-v>=1)
//			dk[v].erase(dk[v].find(abs(p[l-v]-p[l])));
			
		}
		swap(p[l],p[r]);
		swap(wz[p[l]],wz[p[r]]);
		for(int v=1;v<=L;v++){
			if(l+v<=n)
			dk[v].insert(abs(p[l+v]-p[l]));
			if(r+v<=n)
			dk[v].insert(abs(p[r+v]-p[r]));
			if(l+v!=r)
			if(r-v>=1)
			dk[v].insert(abs(p[r-v]-p[r]));
			if(l-v>=1)
			dk[v].insert(abs(p[l-v]-p[l]));
			
			
			
			if(p[l]+v<=n)
			dk[v].insert(abs(l-wz[p[l]+v]));
			if(p[l]-v>=1)
			dk[v].insert(abs(l-wz[p[l]-v]));
			if(p[r]+v!=p[l])
			if(p[r]+v<=n)
			dk[v].insert(abs(r-wz[p[r]+v]));
			if(p[r]-v!=p[l])
			if(p[r]-v>=1)
			dk[v].insert(abs(r-wz[p[r]-v]));
		}
		printf("%lld\n",ask());
//		ans[i]=ask();
		
	}
}
/*
6 5
2 4 1 6 3 5
1 2
3 5
1 2
5 3
5 6
*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9240kb

input:

6 5
2 4 1 6 3 5
1 2
3 5
1 2
5 3
5 6

output:

2
1
1
1
2
1

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 8588kb

input:

10 20
1 4 7 10 2 5 8 3 6 9
10 1
5 7
1 2
5 3
6 3
9 4
3 4
9 6
8 4
9 6
8 7
3 8
10 7
2 7
3 7
5 9
7 6
4 6
2 10
8 9

output:

3
3
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1

result:

ok 21 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8460kb

input:

5 6
1 3 5 2 4
2 4
1 3
2 4
1 4
2 3
4 2

output:

2
1
1
1
1
1
2

result:

ok 7 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 8576kb

input:

4 4
1 3 2 4
1 2
3 1
1 3
2 3

output:

1
1
1
1
1

result:

ok 5 number(s): "1 1 1 1 1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 8556kb

input:

3 5
1 2 3
1 3
2 1
3 2
2 1
2 1

output:

1
1
1
1
1
1

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 13ms
memory: 9844kb

input:

100 1000
1 11 21 31 41 51 61 71 81 91 2 12 22 32 42 52 62 72 82 92 3 13 23 33 43 53 63 73 83 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6 16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 19 29 39 49 59 69 79 89 99 10 20 30 40 50 60 70 80 90 100...

output:

10
10
10
3
3
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2...

result:

ok 1001 numbers

Test #7:

score: 0
Accepted
time: 82ms
memory: 11920kb

input:

1000 1000
1 32 63 94 125 156 187 218 249 280 311 342 373 404 435 466 497 528 559 590 621 652 683 714 745 776 807 838 869 900 931 962 993 2 33 64 95 126 157 188 219 250 281 312 343 374 405 436 467 498 529 560 591 622 653 684 715 746 777 808 839 870 901 932 963 994 3 34 65 96 127 158 189 220 251 282 3...

output:

31
21
21
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
9
9
9
9
9
9
9
9
8
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
...

result:

ok 1001 numbers

Test #8:

score: 0
Accepted
time: 43ms
memory: 9036kb

input:

292 1828
1 18 35 52 69 86 103 120 137 154 171 188 205 222 239 256 273 290 2 19 36 53 70 87 104 121 138 155 172 189 206 223 240 257 274 291 3 20 37 54 71 88 105 122 139 156 173 190 207 224 241 258 275 292 4 21 38 55 72 89 106 123 140 157 174 191 208 225 242 259 276 5 22 39 56 73 90 107 124 141 158 17...

output:

17
9
9
6
6
6
6
6
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

result:

ok 1829 numbers

Test #9:

score: 0
Accepted
time: 355ms
memory: 16388kb

input:

1919 2393
1 44 87 130 173 216 259 302 345 388 431 474 517 560 603 646 689 732 775 818 861 904 947 990 1033 1076 1119 1162 1205 1248 1291 1334 1377 1420 1463 1506 1549 1592 1635 1678 1721 1764 1807 1850 1893 2 45 88 131 174 217 260 303 346 389 432 475 518 561 604 647 690 733 776 819 862 905 948 991 1...

output:

43
43
43
42
42
42
42
42
42
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

result:

ok 2394 numbers

Test #10:

score: 0
Accepted
time: 160ms
memory: 12912kb

input:

1000 2000
1 32 63 94 125 156 187 218 249 280 311 342 373 404 435 466 497 528 559 590 621 652 683 714 745 776 807 838 869 900 931 962 993 2 33 64 95 126 157 188 219 250 281 312 343 374 405 436 467 498 529 560 591 622 653 684 715 746 777 808 839 870 901 932 963 994 3 34 65 96 127 158 189 220 251 282 3...

output:

31
16
16
12
12
12
12
12
12
12
12
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2...

result:

ok 2001 numbers

Test #11:

score: 0
Accepted
time: 35ms
memory: 10468kb

input:

500 999
1 23 45 67 89 111 133 155 177 199 221 243 265 287 309 331 353 375 397 419 441 463 485 2 24 46 68 90 112 134 156 178 200 222 244 266 288 310 332 354 376 398 420 442 464 486 3 25 47 69 91 113 135 157 179 201 223 245 267 289 311 333 355 377 399 421 443 465 487 4 26 48 70 92 114 136 158 180 202 ...

output:

22
22
22
19
19
16
16
12
12
12
8
8
8
8
8
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 245ms
memory: 14536kb

input:

1600 2000
1 41 81 121 161 201 241 281 321 361 401 441 481 521 561 601 641 681 721 761 801 841 881 921 961 1001 1041 1081 1121 1161 1201 1241 1281 1321 1361 1401 1441 1481 1521 1561 2 42 82 122 162 202 242 282 322 362 402 442 482 522 562 602 642 682 722 762 802 842 882 922 962 1002 1042 1082 1122 116...

output:

40
40
40
40
40
40
40
36
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result:

ok 2001 numbers

Test #13:

score: 0
Accepted
time: 240ms
memory: 14524kb

input:

1600 2000
1 41 81 121 161 201 241 281 321 361 401 441 481 521 561 601 641 681 721 761 801 841 881 921 961 1001 1041 1081 1121 1161 1201 1241 1281 1321 1361 1401 1441 1481 1521 1561 2 42 82 122 162 202 242 282 322 362 402 442 482 522 562 602 642 682 722 762 802 842 882 922 962 1002 1042 1082 1122 116...

output:

40
40
40
40
40
40
40
18
15
15
15
15
15
15
15
15
15
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2...

result:

ok 2001 numbers

Test #14:

score: 0
Accepted
time: 65ms
memory: 11512kb

input:

900 900
1 31 61 91 121 151 181 211 241 271 301 331 361 391 421 451 481 511 541 571 601 631 661 691 721 751 781 811 841 871 2 32 62 92 122 152 182 212 242 272 302 332 362 392 422 452 482 512 542 572 602 632 662 692 722 752 782 812 842 872 3 33 63 93 123 153 183 213 243 273 303 333 363 393 423 453 483...

output:

30
30
30
18
18
18
18
18
18
18
8
8
8
8
7
7
7
7
7
7
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 901 numbers

Test #15:

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

input:

400 500
1 21 41 61 81 101 121 141 161 181 201 221 241 261 281 301 321 341 361 381 2 22 42 62 82 102 122 142 162 182 202 222 242 262 282 302 322 342 362 382 3 23 43 63 83 103 123 143 163 183 203 223 243 263 283 303 323 343 363 383 4 24 44 64 84 104 124 144 164 184 204 224 244 264 284 304 324 344 364 ...

output:

20
20
16
13
13
13
13
13
13
6
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

result:

ok 501 numbers

Test #16:

score: 0
Accepted
time: 18ms
memory: 10516kb

input:

400 500
1 21 41 61 81 101 121 141 161 181 201 221 241 261 281 301 321 341 361 381 2 22 42 62 82 102 122 142 162 182 202 222 242 262 282 302 322 342 362 382 3 23 43 63 83 103 123 143 163 183 203 223 243 263 283 303 323 343 363 383 4 24 44 64 84 104 124 144 164 184 204 224 244 264 284 304 324 344 364 ...

output:

20
19
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 501 numbers

Test #17:

score: -100
Time Limit Exceeded

input:

100000 100000
1 317 633 949 1265 1581 1897 2213 2529 2845 3161 3477 3793 4109 4425 4741 5057 5373 5689 6005 6321 6637 6953 7269 7585 7901 8217 8533 8849 9165 9481 9797 10113 10429 10745 11061 11377 11693 12009 12325 12641 12957 13273 13589 13905 14221 14537 14853 15169 15485 15801 16117 16433 16749 ...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 02:50:47 | 开源项目