QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#703114#8236. Snake Movewang_xyAC ✓1497ms543892kbC++142.1kb2024-11-02 17:11:582024-11-02 17:12:06

Judging History

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

  • [2024-11-02 17:12:06]
  • 评测
  • 测评结果:AC
  • 用时:1497ms
  • 内存:543892kb
  • [2024-11-02 17:11:58]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>P;
const int maxn=3e3+5;
const int inf=0x3f3f3f3f;
int n,m,k;
char s[maxn][maxn];
int d[maxn*maxn];
vector<int>G[maxn*maxn];
int tag[maxn*maxn];
int mov[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int root;
inline int id(int r,int c){
	return (r-1)*m+c;
}
signed main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		tag[id(x,y)]=k+1-i;
		if(i==1){
			root=id(x,y);
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
	}

	// if(n>10&&m>10){
	// 	return 0;
	// }

	//memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			d[id(i,j)]=inf;
		}
	}
	d[root]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='#'){
				continue;
			}
			int u=id(i,j);
			for(int k=0;k<4;k++){
				int I=i+mov[k][0];
				int J=j+mov[k][1];
				if(I<1||I>n||J<1||J>m||s[I][J]=='#'){
					continue;
				}
				G[u].push_back(id(I,J));
			}
		}
	}
	queue<int>q1,q2;
	q1.push(root);
	int cnt=0;

	// if(n>10&&m>10){
	// 	return 0;
	// }

	while(!q1.empty()||!q2.empty()){
		++cnt;
		if(cnt>=2*n*m){
			printf("NO\n");
			return 0;
		}
		int D=inf;
		if(!q1.empty()){
			int v=q1.front();
			if(d[v]<D){
				D=d[v];
			}
		}
		if(!q2.empty()){
			int v=q2.front();
			if(d[v]<D){
				D=d[v];
			}
		}
		if(D==inf){
			break;
		}
		int u=-1;
		if(!q1.empty()&&d[q1.front()]==D){
			u=q1.front();
			q1.pop();
		}
		else{
			u=q2.front();
			q2.pop();
		}
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			int D=max(d[u],tag[v]-1)+1;
			if(D>=d[v]){
				continue;
			}
			d[v]=D;
			if(tag[v]==0){
				q1.push(v);
			}
			else{
				q2.push(v);
			}
		}
	}
	// if(cnt>=2*n*m){
	// 	printf("NO\n");
	// }
	unsigned long long ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=id(i,j);
			if(d[x]==inf){
				continue;
			}
			ans+=(unsigned long long)d[x]*(unsigned long long)d[x];
		}
	}
	printf("%llu",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 36ms
memory: 218836kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 28ms
memory: 218820kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 24ms
memory: 218812kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 990ms
memory: 532424kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 887ms
memory: 450240kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 419ms
memory: 392276kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 211ms
memory: 323632kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1092ms
memory: 530360kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 911ms
memory: 455316kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: 0
Accepted
time: 399ms
memory: 387540kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

40571

result:

ok single line: '40571'

Test #11:

score: 0
Accepted
time: 199ms
memory: 323612kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

2705

result:

ok single line: '2705'

Test #12:

score: 0
Accepted
time: 1149ms
memory: 541932kb

input:

3000 3000 100
2573 1917
2572 1917
2572 1916
2573 1916
2574 1916
2574 1915
2573 1915
2572 1915
2571 1915
2571 1914
2570 1914
2570 1915
2569 1915
2569 1916
2568 1916
2568 1917
2569 1917
2570 1917
2570 1916
2571 1916
2571 1917
2571 1918
2570 1918
2569 1918
2569 1919
2570 1919
2571 1919
2571 1920
2572 1...

output:

41693682087973

result:

ok single line: '41693682087973'

Test #13:

score: 0
Accepted
time: 805ms
memory: 450044kb

input:

3000 2900 56
923 228
922 228
921 228
920 228
919 228
919 227
919 226
920 226
920 227
921 227
922 227
922 226
922 225
921 225
921 224
921 223
920 223
920 222
920 221
921 221
921 222
922 222
923 222
924 222
925 222
925 223
924 223
923 223
922 223
922 224
923 224
923 225
924 225
924 224
925 224
925 225...

output:

36262204093655

result:

ok single line: '36262204093655'

Test #14:

score: 0
Accepted
time: 407ms
memory: 389244kb

input:

2900 3000 100
2357 817
2357 818
2357 819
2358 819
2359 819
2360 819
2360 820
2361 820
2361 819
2361 818
2360 818
2360 817
2361 817
2362 817
2362 818
2363 818
2364 818
2365 818
2365 817
2364 817
2363 817
2363 816
2363 815
2362 815
2362 814
2361 814
2361 815
2360 815
2360 816
2359 816
2358 816
2358 81...

output:

4878972

result:

ok single line: '4878972'

Test #15:

score: 0
Accepted
time: 204ms
memory: 325068kb

input:

3000 3000 97
2987 2472
2986 2472
2986 2471
2985 2471
2985 2470
2985 2469
2984 2469
2983 2469
2983 2468
2982 2468
2981 2468
2980 2468
2979 2468
2978 2468
2977 2468
2977 2469
2978 2469
2978 2470
2977 2470
2976 2470
2976 2471
2977 2471
2977 2472
2978 2472
2978 2473
2977 2473
2976 2473
2976 2472
2975 24...

output:

1992372

result:

ok single line: '1992372'

Test #16:

score: 0
Accepted
time: 1258ms
memory: 532172kb

input:

3000 2900 22
2673 1308
2673 1309
2673 1310
2672 1310
2672 1309
2672 1308
2672 1307
2671 1307
2671 1306
2671 1305
2672 1305
2672 1306
2673 1306
2674 1306
2674 1305
2675 1305
2675 1306
2675 1307
2675 1308
2674 1308
2674 1307
2673 1307
......................................................................

output:

39910190747333

result:

ok single line: '39910190747333'

Test #17:

score: 0
Accepted
time: 922ms
memory: 451100kb

input:

2900 3000 72
820 2426
820 2427
820 2428
820 2429
820 2430
821 2430
821 2429
821 2428
822 2428
822 2429
822 2430
823 2430
824 2430
824 2429
824 2428
825 2428
825 2427
824 2427
824 2426
824 2425
825 2425
825 2426
826 2426
827 2426
828 2426
828 2427
829 2427
829 2426
830 2426
830 2427
830 2428
830 2429...

output:

30022933538350

result:

ok single line: '30022933538350'

Test #18:

score: 0
Accepted
time: 408ms
memory: 392932kb

input:

3000 3000 77
2008 1630
2007 1630
2007 1629
2007 1628
2006 1628
2005 1628
2004 1628
2004 1629
2003 1629
2002 1629
2001 1629
2001 1628
2000 1628
2000 1627
2000 1626
1999 1626
1999 1627
1999 1628
1999 1629
1999 1630
1999 1631
1999 1632
2000 1632
2000 1633
2000 1634
2001 1634
2001 1635
2001 1636
2002 16...

output:

385875

result:

ok single line: '385875'

Test #19:

score: 0
Accepted
time: 193ms
memory: 323792kb

input:

3000 2900 31
1343 2185
1342 2185
1342 2184
1341 2184
1341 2185
1341 2186
1341 2187
1340 2187
1340 2188
1339 2188
1338 2188
1337 2188
1336 2188
1336 2187
1337 2187
1337 2186
1337 2185
1337 2184
1338 2184
1338 2183
1337 2183
1336 2183
1335 2183
1335 2184
1334 2184
1334 2185
1334 2186
1335 2186
1335 21...

output:

97830

result:

ok single line: '97830'

Test #20:

score: 0
Accepted
time: 1037ms
memory: 531476kb

input:

2900 3000 113
551 1058
551 1057
552 1057
552 1056
553 1056
553 1055
552 1055
551 1055
551 1054
552 1054
552 1053
552 1052
552 1051
551 1051
551 1052
551 1053
550 1053
550 1052
549 1052
549 1051
548 1051
548 1050
547 1050
547 1051
546 1051
545 1051
545 1050
545 1049
545 1048
544 1048
544 1049
544 105...

output:

35257969420026

result:

ok single line: '35257969420026'

Test #21:

score: 0
Accepted
time: 1497ms
memory: 513852kb

input:

3000 3000 43
734 2607
733 2607
733 2608
733 2609
732 2609
732 2610
733 2610
734 2610
734 2609
734 2608
735 2608
735 2607
735 2606
735 2605
736 2605
736 2604
735 2604
734 2604
734 2603
735 2603
735 2602
735 2601
734 2601
734 2602
733 2602
733 2603
732 2603
731 2603
730 2603
730 2604
730 2605
730 2606...

output:

44813406952069

result:

ok single line: '44813406952069'

Test #22:

score: 0
Accepted
time: 982ms
memory: 477316kb

input:

3000 2900 31
2017 1649
2016 1649
2016 1648
2016 1647
2017 1647
2017 1646
2017 1645
2016 1645
2015 1645
2014 1645
2014 1644
2015 1644
2015 1643
2014 1643
2013 1643
2013 1644
2013 1645
2013 1646
2014 1646
2014 1647
2014 1648
2013 1648
2013 1649
2014 1649
2014 1650
2015 1650
2015 1649
2015 1648
2015 16...

output:

21058834151672

result:

ok single line: '21058834151672'

Test #23:

score: 0
Accepted
time: 944ms
memory: 449856kb

input:

2900 3000 28
1314 1304
1313 1304
1312 1304
1312 1305
1311 1305
1311 1304
1311 1303
1310 1303
1310 1304
1310 1305
1310 1306
1311 1306
1311 1307
1312 1307
1312 1308
1312 1309
1313 1309
1313 1310
1312 1310
1311 1310
1311 1309
1311 1308
1310 1308
1309 1308
1309 1309
1309 1310
1310 1310
1310 1309
..##..#...

output:

17072462334840

result:

ok single line: '17072462334840'

Test #24:

score: 0
Accepted
time: 473ms
memory: 424584kb

input:

3000 3000 150
1859 868
1860 868
1860 867
1859 867
1859 866
1859 865
1858 865
1858 866
1857 866
1857 865
1856 865
1856 864
1856 863
1856 862
1856 861
1856 860
1856 859
1857 859
1857 858
1858 858
1859 858
1859 859
1858 859
1858 860
1859 860
1860 860
1860 861
1859 861
1858 861
1858 862
1858 863
1857 86...

output:

450198912

result:

ok single line: '450198912'

Test #25:

score: 0
Accepted
time: 394ms
memory: 388624kb

input:

3000 2900 70
358 1006
359 1006
359 1005
358 1005
357 1005
357 1004
358 1004
358 1003
358 1002
359 1002
359 1003
359 1004
360 1004
361 1004
361 1003
360 1003
360 1002
360 1001
360 1000
359 1000
359 999
358 999
358 1000
357 1000
357 999
356 999
355 999
355 1000
356 1000
356 1001
356 1002
356 1003
355 ...

output:

379808

result:

ok single line: '379808'

Test #26:

score: 0
Accepted
time: 309ms
memory: 355756kb

input:

2900 3000 29
1355 1861
1356 1861
1356 1862
1355 1862
1355 1863
1354 1863
1354 1862
1353 1862
1352 1862
1352 1863
1351 1863
1351 1864
1351 1865
1351 1866
1352 1866
1352 1867
1351 1867
1351 1868
1352 1868
1352 1869
1353 1869
1353 1868
1353 1867
1354 1867
1354 1866
1353 1866
1353 1865
1353 1864
1353 18...

output:

59874

result:

ok single line: '59874'

Test #27:

score: 0
Accepted
time: 205ms
memory: 325460kb

input:

3000 3000 141
200 2617
201 2617
201 2618
202 2618
203 2618
203 2617
202 2617
202 2616
201 2616
201 2615
201 2614
201 2613
200 2613
200 2614
199 2614
198 2614
198 2613
197 2613
197 2614
196 2614
196 2615
196 2616
197 2616
197 2617
197 2618
198 2618
198 2619
197 2619
196 2619
196 2620
195 2620
195 262...

output:

3979414

result:

ok single line: '3979414'

Test #28:

score: 0
Accepted
time: 128ms
memory: 294488kb

input:

3000 2900 26
2187 2667
2187 2666
2188 2666
2188 2667
2189 2667
2189 2666
2189 2665
2189 2664
2188 2664
2188 2663
2189 2663
2190 2663
2190 2662
2189 2662
2189 2661
2190 2661
2190 2660
2190 2659
2190 2658
2191 2658
2191 2657
2191 2656
2190 2656
2189 2656
2189 2657
2190 2657
..#.####.##.####.#.###.####...

output:

32020

result:

ok single line: '32020'

Test #29:

score: 0
Accepted
time: 96ms
memory: 271648kb

input:

2900 3000 258
688 610
688 609
688 608
687 608
686 608
685 608
685 607
685 606
684 606
684 605
685 605
686 605
687 605
687 604
688 604
688 603
689 603
689 602
688 602
687 602
687 603
686 603
686 602
686 601
687 601
687 600
688 600
688 599
687 599
686 599
686 600
685 600
685 599
684 599
684 598
683 59...

output:

27653531

result:

ok single line: '27653531'

Test #30:

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

input:

3000 3000 24
2542 2486
2541 2486
2541 2485
2540 2485
2539 2485
2539 2484
2540 2484
2540 2483
2539 2483
2539 2482
2538 2482
2537 2482
2536 2482
2536 2481
2536 2480
2536 2479
2537 2479
2538 2479
2539 2479
2539 2480
2538 2480
2538 2481
2537 2481
2537 2480
###############################################...

output:

21108

result:

ok single line: '21108'

Test #31:

score: 0
Accepted
time: 1101ms
memory: 542508kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

363537285683354

result:

ok single line: '363537285683354'

Test #32:

score: 0
Accepted
time: 1061ms
memory: 514172kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

360776872211011

result:

ok single line: '360776872211011'

Test #33:

score: 0
Accepted
time: 1339ms
memory: 487124kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

70861586029764531

result:

ok single line: '70861586029764531'

Test #34:

score: 0
Accepted
time: 1087ms
memory: 458864kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

358016319444845

result:

ok single line: '358016319444845'

Test #35:

score: 0
Accepted
time: 754ms
memory: 427864kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

25377840152461713

result:

ok single line: '25377840152461713'

Test #36:

score: 0
Accepted
time: 410ms
memory: 394596kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

1022640441833917

result:

ok single line: '1022640441833917'

Test #37:

score: 0
Accepted
time: 326ms
memory: 362832kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

993822955282599

result:

ok single line: '993822955282599'

Test #38:

score: 0
Accepted
time: 227ms
memory: 328308kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

982158599297341

result:

ok single line: '982158599297341'

Test #39:

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

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

977428147407433

result:

ok single line: '977428147407433'

Test #40:

score: 0
Accepted
time: 113ms
memory: 275596kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

973680318434648

result:

ok single line: '973680318434648'

Test #41:

score: 0
Accepted
time: 70ms
memory: 267016kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

971365897119396

result:

ok single line: '971365897119396'

Test #42:

score: 0
Accepted
time: 1082ms
memory: 543892kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

91794863372501516

result:

ok single line: '91794863372501516'

Test #43:

score: 0
Accepted
time: 1166ms
memory: 518356kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

82700945652408184

result:

ok single line: '82700945652408184'

Test #44:

score: 0
Accepted
time: 1010ms
memory: 490508kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

73500269654805059

result:

ok single line: '73500269654805059'

Test #45:

score: 0
Accepted
time: 957ms
memory: 461696kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

63384741140556828

result:

ok single line: '63384741140556828'

Test #46:

score: 0
Accepted
time: 744ms
memory: 430208kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

34956324046973487

result:

ok single line: '34956324046973487'

Test #47:

score: 0
Accepted
time: 428ms
memory: 398176kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1041661166759288

result:

ok single line: '1041661166759288'

Test #48:

score: 0
Accepted
time: 334ms
memory: 366236kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1016347332472313

result:

ok single line: '1016347332472313'

Test #49:

score: 0
Accepted
time: 243ms
memory: 331260kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1008792357484897

result:

ok single line: '1008792357484897'

Test #50:

score: 0
Accepted
time: 147ms
memory: 302112kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1006712603164211

result:

ok single line: '1006712603164211'

Test #51:

score: 0
Accepted
time: 106ms
memory: 279756kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1004341806374727

result:

ok single line: '1004341806374727'

Test #52:

score: 0
Accepted
time: 73ms
memory: 268156kb

input:

3000 3000 100000
1500 1500
1500 1501
1499 1501
1499 1500
1499 1499
1500 1499
1501 1499
1501 1500
1501 1501
1501 1502
1500 1502
1499 1502
1498 1502
1498 1501
1498 1500
1498 1499
1498 1498
1499 1498
1500 1498
1501 1498
1502 1498
1502 1499
1502 1500
1502 1501
1502 1502
1502 1503
1501 1503
1500 1503
149...

output:

1003015475942796

result:

ok single line: '1003015475942796'

Test #53:

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

input:

1 3000 3000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 ...

output:

62923530496

result:

ok single line: '62923530496'

Test #54:

score: 0
Accepted
time: 54ms
memory: 228748kb

input:

3000 1 3000
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
50 1
51 1
52 1
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60...

output:

62923530496

result:

ok single line: '62923530496'

Test #55:

score: 0
Accepted
time: 27ms
memory: 219172kb

input:

1 3000 3000
1 3000
1 2999
1 2998
1 2997
1 2996
1 2995
1 2994
1 2993
1 2992
1 2991
1 2990
1 2989
1 2988
1 2987
1 2986
1 2985
1 2984
1 2983
1 2982
1 2981
1 2980
1 2979
1 2978
1 2977
1 2976
1 2975
1 2974
1 2973
1 2972
1 2971
1 2970
1 2969
1 2968
1 2967
1 2966
1 2965
1 2964
1 2963
1 2962
1 2961
1 2960
1...

output:

62923530496

result:

ok single line: '62923530496'

Test #56:

score: 0
Accepted
time: 23ms
memory: 228552kb

input:

3000 1 3000
3000 1
2999 1
2998 1
2997 1
2996 1
2995 1
2994 1
2993 1
2992 1
2991 1
2990 1
2989 1
2988 1
2987 1
2986 1
2985 1
2984 1
2983 1
2982 1
2981 1
2980 1
2979 1
2978 1
2977 1
2976 1
2975 1
2974 1
2973 1
2972 1
2971 1
2970 1
2969 1
2968 1
2967 1
2966 1
2965 1
2964 1
2963 1
2962 1
2961 1
2960 1
2...

output:

62923530496

result:

ok single line: '62923530496'

Test #57:

score: 0
Accepted
time: 20ms
memory: 219096kb

input:

1 1 1
1 1
.

output:

0

result:

ok single line: '0'

Test #58:

score: 0
Accepted
time: 315ms
memory: 402616kb

input:

3000 3000 100000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 ...

output:

14029953357937982630

result:

ok single line: '14029953357937982630'

Extra Test:

score: 0
Extra Test Passed