QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56363#2170. Space WallsUT_aka_IsAC ✓3354ms560048kbC++4.8kb2022-10-18 22:46:542022-10-18 22:46:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-18 22:46:56]
  • 评测
  • 测评结果:AC
  • 用时:3354ms
  • 内存:560048kb
  • [2022-10-18 22:46:54]
  • 提交

answer

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

typedef long long ll;

#define int long long

#define fr first
#define sc second
#define mp make_pair

template<class t=ll>
t extgcd(t a,t b,t&x,t&y){
	if(b==0){
		x=1;y=0;return a;
	}
	else{
		t g=extgcd(b,a%b,y,x);
		y-=a/b*x;
		return g;
	}
}
template<class t=ll>
pair<t,t> modinv(t x,t m){
	t a,b;
	t g=extgcd(x,m,a,b);
	if(a<0)a+=m/g;
	return {g,a};
}

ll crt(ll r1,ll t1,ll r2,ll t2){
	int a=t1,b=r1,c=t2,d=r2;
	if(b<d){
		swap(a,c);
		swap(b,d);
	}
	c%=d;
	int g,e;
	tie(g,e)=modinv(b,d);
	int k=(c-a);
	if(k%g)return -1;
	k/=g;
	int m=b/g*d;
	int x=(a+k*e%(d/g)*b)%m;
	if(x<0)x+=m;
	return x;
}

int dir(string s){
	int ret=s[0]-'x';
	if(s[1]=='-')ret+=3;
	return ret;
}

int n,k;
int x1[3][102],x2[3][102];
int mx[3][102];
string ms[102],mt[102];

int used[402][402][402];
//vector<pair<int,int>> v[402][402][402][6];
vector<pair<int,pair<int,int>>> v;

bool U(int x,int y,int z){
	if(x<0||y<0||z<0)return false;
	return used[x][y][z];
}

int ee(int f,int d){
	int e;
	if((f+1)%3==d%3)e=(f+2)%3;
	else e=(f+1)%3+3;
	if(f>=3)e+=3; if(d>=3)e+=3;
	return e%6;
}

signed main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++)cin>>x1[j][i];
		for(int j=0;j<3;j++)cin>>x2[j][i];
	}
	for(int i=0;i<k;i++){
		for(int j=0;j<3;j++)cin>>mx[j][i];
		cin>>ms[i]>>mt[i];
	}
	
	vector<int> X[3];
	for(int t=0;t<3;t++){
		for(int i=0;i<n;i++){
			X[t].push_back(x1[t][i]);
			X[t].push_back(x2[t][i]);
		}
		for(int i=0;i<k;i++){
			X[t].push_back(mx[t][i]);
			X[t].push_back(mx[t][i]+1);
		}
		sort(X[t].begin(),X[t].end());
		X[t].erase(unique(X[t].begin(),X[t].end()),X[t].end());
	}
	auto lb=[&](int t,int x){
		return lower_bound(X[t].begin(),X[t].end(),x)-X[t].begin();
	};
	
	for(int i=0;i<n;i++){
		int x[2][3];
		for(int t=0;t<3;t++){
			x[0][t]=lb(t,x1[t][i]);
			x[1][t]=lb(t,x2[t][i]);
		}
		used[x[0][0]][x[0][1]][x[0][2]]++;
		used[x[0][0]][x[0][1]][x[1][2]]--;
		used[x[0][0]][x[1][1]][x[0][2]]--;
		used[x[0][0]][x[1][1]][x[1][2]]++;
		used[x[1][0]][x[0][1]][x[0][2]]--;
		used[x[1][0]][x[0][1]][x[1][2]]++;
		used[x[1][0]][x[1][1]][x[0][2]]++;
		used[x[1][0]][x[1][1]][x[1][2]]--;
	}
	for(int i=0;i<402;i++)for(int j=0;j<402;j++)for(int k_=1;k_<402;k_++){
		used[i][j][k_]+=used[i][j][k_-1];
	}
	for(int i=0;i<402;i++)for(int j=1;j<402;j++)for(int k_=0;k_<402;k_++){
		used[i][j][k_]+=used[i][j-1][k_];
	}
	for(int i=1;i<402;i++)for(int j=0;j<402;j++)for(int k_=0;k_<402;k_++){
		used[i][j][k_]+=used[i-1][j][k_];
	}
	int r[102];
	int e[102];
	//cerr<<__LINE__<<endl;
	for(int i=0;i<k;i++){
		int sx[3],x[3];
		for(int t=0;t<3;t++)sx[t]=x[t]=lb(t,mx[t][i]);
		int f=dir(ms[i]); int sf=f;
		int d=dir(mt[i]);
		e[i]=ee(f,d);
		int ti=0;
		do{
			//static int cnt=0; if(cnt++>=100)return 0;
			//v[x[0]][x[1]][x[2]][f].push_back(mp(i,ti));
			v.push_back(mp(((x[0]*500+x[1])*500+x[2])*500+f,mp(i,ti)));
			//cerr<<i<<" "<<ti<<" "<<x[0]<<" "<<x[1]<<" "<<x[2]<<" "<<f<<" "<<d<<endl;
			ti+=X[d%3][x[d%3]+1]-X[d%3][x[d%3]];
			int nx[3]={x[0],x[1],x[2]};
			if(d<3)nx[d]++;
			else nx[d-3]--;
			if(f<3)nx[f]++;
			else nx[f-3]--;
			if(U(nx[0],nx[1],nx[2])){
				for(int t=0;t<3;t++)x[t]=nx[t];
				int d_=d;
				d=f;
				f=(d_+3)%6;
			}
			else {
				if(f<3)nx[f]--;
				else nx[f-3]++;
				if(U(nx[0],nx[1],nx[2])){
					for(int t=0;t<3;t++)x[t]=nx[t];
				}
				else {
					int d_=d;
					d=(f+3)%6;
					f=d_;
				}
			}
		}while(sx[0]!=x[0]||sx[1]!=x[1]||sx[2]!=x[2]||sf!=f);
		r[i]=ti;
	}
	//cerr<<__LINE__<<endl;
	int ret=-1;
	/*for(int i=0;i<402;i++)for(int j=0;j<402;j++)for(int x=0;x<402;x++)for(int t=0;t<6;t++){
		auto v_=v[i][j][x][t];
		for(int y=0;y<(int)v_.size();y++)for(int z=y+1;z<(int)v_.size();z++){
			int ret_=crt(r[v_[y].fr],v_[y].sc,r[v_[z].fr],v_[z].sc);
			if(ret_==-1||ret==-1)ret=ret+ret_+1;
			else ret=min(ret,ret_);
		}
	}*/
	sort(v.begin(),v.end());
	for(int i=0;i<(int)v.size();i++){
		int ni=i;
		while(ni<v.size()&&v[ni].fr==v[i].fr)ni++;
		for(int j1=i;j1<ni;j1++)for(int j2=j1+1;j2<ni;j2++){
			auto p=v[j1].sc;
			auto q=v[j2].sc;
			//cerr<<p.fr<<" "<<p.sc<<" "<<q.fr<<" "<<q.sc<<endl;
			int ret_=crt(r[p.fr],p.sc,r[q.fr],q.sc);
			if(ret_==-1||ret==-1)ret=ret+ret_+1;
			else ret=min(ret,ret_);
			//cerr<<e[p.fr]<<" "<<p.sc<<" "<<e[q.fr]<<" "<<q.sc<<endl;
			/*if(max(e[p.fr],e[q.fr])-min(e[p.fr],e[q.fr])==3
			&&abs(p.sc-q.sc)==1){
				if(ret==-1)ret=min(p.sc,q.sc);
				else ret=min(ret,min(p.sc,q.sc));
			}*/
			if(max(e[p.fr],e[q.fr])-min(e[p.fr],e[q.fr])==3){
				int dd=ee(e[p.fr],v[j1].fr%500)%3;
				int xx[3];
				xx[2]=v[j1].fr/500;
				xx[1]=xx[2]/500;
				xx[0]=xx[1]/500;
				xx[1]%=500;
				xx[2]%=500;
				dd=X[dd][xx[dd]+1]-X[dd][xx[dd]];
				int A=p.sc; int B=p.sc+dd-1;
				int C=q.sc; int D=q.sc+dd-1;
				//cerr<<A<<" "<<B<<" "<<C<<" "<<D<<endl;
				if(max(A,C)<=min(B,D)+1){
					if(ret==-1)ret=(max(A,C)+min(B,D))/2;
					else ret=min(ret,(max(A,C)+min(B,D))/2);
				}
			}
		}
	}
	if(ret==-1)puts("ok");
	else cout<<ret<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 248ms
memory: 511164kb

input:

6 3
0 0 0 1 3 3
0 0 0 3 1 3
0 0 0 3 3 1
2 0 0 3 3 3
0 2 0 3 3 3
0 0 2 3 3 3
0 1 1 x+ z+
1 2 1 y- z-
1 1 0 z+ x+

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 250ms
memory: 511108kb

input:

6 3
0 0 0 1 3 3
0 0 0 3 1 3
0 0 0 3 3 1
2 0 0 3 3 3
0 2 0 3 3 3
0 0 2 3 3 3
0 1 1 x+ z+
1 2 1 y- z-
1 1 0 z+ x-

output:

ok

result:

ok single line: 'ok'

Test #3:

score: 0
Accepted
time: 604ms
memory: 560048kb

input:

100 100
0 0 0 1001 997 1
0 0 0 1 997 1007
0 0 0 1001 1 1007
0 2 0 1001 3 1007
0 4 0 1001 5 1007
0 6 0 1001 7 1007
0 8 0 1001 9 1007
0 10 0 1001 11 1007
0 12 0 1001 13 1007
0 14 0 1001 15 1007
0 16 0 1001 17 1007
0 18 0 1001 19 1007
0 20 0 1001 21 1007
0 22 0 1001 23 1007
0 24 0 1001 25 1007
0 26 0 1...

output:

1801

result:

ok single line: '1801'

Test #4:

score: 0
Accepted
time: 3354ms
memory: 512540kb

input:

100 100
0 0 0 999 999 1
999 999 0 1998 1998 1
1998 1998 0 2997 2997 1
2997 2997 0 3996 3996 1
3996 3996 0 4995 4995 1
4995 4995 0 5994 5994 1
5994 5994 0 6993 6993 1
6993 6993 0 7992 7992 1
7992 7992 0 8991 8991 1
8991 8991 0 9990 9990 1
9990 9990 0 10989 10989 1
10989 10989 0 11988 11988 1
11988 11...

output:

199750

result:

ok single line: '199750'

Test #5:

score: 0
Accepted
time: 197ms
memory: 511284kb

input:

100 2
0 0 318585 1000000 1000000 318586
0 0 73277 1000000 1000000 73278
0 0 742493 1000000 1000000 742494
0 0 285149 1000000 1000000 285150
0 0 197706 1000000 1000000 197707
0 0 305168 1000000 1000000 305169
0 0 533430 1000000 1000000 533431
0 0 736391 1000000 1000000 736392
0 0 570675 1000000 10000...

output:

9999857800129751

result:

ok single line: '9999857800129751'

Test #6:

score: 0
Accepted
time: 1187ms
memory: 514028kb

input:

100 100
0 0 318585 1000000 1000000 318586
0 0 73277 1000000 1000000 73278
0 0 742493 1000000 1000000 742494
0 0 285149 1000000 1000000 285150
0 0 197706 1000000 1000000 197707
0 0 305168 1000000 1000000 305169
0 0 533430 1000000 1000000 533431
0 0 736391 1000000 1000000 736392
0 0 570675 1000000 100...

output:

19999950799029055

result:

ok single line: '19999950799029055'

Test #7:

score: 0
Accepted
time: 246ms
memory: 511136kb

input:

100 2
0 0 318585 1000000 1000000 318586
0 0 73277 1000000 1000000 73278
0 0 742493 1000000 1000000 742494
0 0 285149 1000000 1000000 285150
0 0 197706 1000000 1000000 197707
0 0 305168 1000000 1000000 305169
0 0 533430 1000000 1000000 533431
0 0 736391 1000000 1000000 736392
0 0 570675 1000000 10000...

output:

19999960599019402

result:

ok single line: '19999960599019402'

Test #8:

score: 0
Accepted
time: 1191ms
memory: 513964kb

input:

100 100
0 0 318585 1000000 1000000 318586
0 0 73277 1000000 1000000 73278
0 0 742493 1000000 1000000 742494
0 0 285149 1000000 1000000 285150
0 0 197706 1000000 1000000 197707
0 0 305168 1000000 1000000 305169
0 0 533430 1000000 1000000 533431
0 0 736391 1000000 1000000 736392
0 0 570675 1000000 100...

output:

99999877

result:

ok single line: '99999877'

Test #9:

score: 0
Accepted
time: 238ms
memory: 511220kb

input:

2 0
1 1 1 2 2 2
4 4 4 5 5 5

output:

ok

result:

ok single line: 'ok'

Test #10:

score: 0
Accepted
time: 218ms
memory: 511304kb

input:

100 100
367 541 994 434 547 1061
6 16 423 12 100 461
140 711 478 190 796 509
281 486 842 314 535 935
232 888 824 303 958 864
157 933 245 230 1026 277
978 884 290 1060 945 295
796 761 151 886 850 199
907 15 785 988 67 838
624 389 442 695 442 475
186 746 427 227 824 472
508 692 543 604 779 643
103 163...

output:

127

result:

ok single line: '127'

Test #11:

score: 0
Accepted
time: 278ms
memory: 511168kb

input:

100 100
375 655 664 390 727 768
473 316 216 494 331 251
148 542 861 232 543 887
857 104 298 934 192 334
553 609 14 557 649 130
93 218 955 134 324 1032
824 196 270 864 262 389
551 951 895 581 1012 942
576 915 228 689 1035 300
849 217 89 959 240 172
751 328 836 802 391 893
942 599 149 992 675 182
544 ...

output:

406

result:

ok single line: '406'

Test #12:

score: 0
Accepted
time: 249ms
memory: 511436kb

input:

100 100
383 120 982 386 165 1094
941 968 8 1045 1075 148
155 21 244 260 69 365
432 722 105 464 748 184
522 329 853 538 387 957
381 503 313 389 589 424
319 508 898 366 520 924
955 141 640 957 274 646
893 815 670 978 894 749
75 396 89 184 421 149
315 558 244 328 565 361
25 155 108 77 180 247
985 791 6...

output:

172

result:

ok single line: '172'

Test #13:

score: 0
Accepted
time: 276ms
memory: 511428kb

input:

100 100
40 390 71 124 465 84
389 729 236 423 732 414
292 259 801 372 374 920
790 612 450 808 674 641
30 31 442 140 118 484
556 572 347 584 764 503
313 910 448 408 1003 496
743 117 301 777 272 384
316 556 530 426 583 657
772 439 143 915 470 271
540 4 27 691 123 144
112 803 792 216 833 917
397 86 562 ...

output:

1512

result:

ok single line: '1512'

Test #14:

score: 0
Accepted
time: 261ms
memory: 511728kb

input:

100 100
9 231 391 161 236 566
870 178 714 1107 355 911
613 287 268 791 465 515
488 140 275 508 280 321
99 149 31 199 391 218
402 783 210 500 1069 361
983 661 880 1089 699 1130
424 708 675 662 929 775
344 956 761 485 1110 1048
221 427 849 269 653 1134
931 29 98 966 257 320
726 229 663 1018 233 782
63...

output:

2232

result:

ok single line: '2232'

Test #15:

score: 0
Accepted
time: 323ms
memory: 513976kb

input:

100 100
829 466 400 1201 811 645
368 379 548 767 736 638
964 930 606 1034 975 613
57 259 303 225 534 525
127 394 786 256 597 1097
81 330 36 412 506 335
760 118 318 870 444 667
679 676 347 721 996 702
429 705 41 499 1044 284
237 873 260 281 1204 503
916 608 515 1193 917 789
618 957 530 790 1217 597
9...

output:

269

result:

ok single line: '269'

Test #16:

score: 0
Accepted
time: 293ms
memory: 517120kb

input:

100 100
619 894 730 1079 910 1056
346 678 860 362 889 1115
636 602 410 1048 629 552
323 553 156 792 740 162
224 757 129 320 1076 357
607 736 373 794 1197 614
207 679 187 583 990 636
614 587 745 1064 1020 823
542 855 904 924 1058 912
54 659 25 546 890 284
292 564 3 748 862 234
475 111 619 567 349 629...

output:

3891

result:

ok single line: '3891'

Test #17:

score: 0
Accepted
time: 248ms
memory: 511344kb

input:

100 100
2684 1219 1493 3393 1263 2206
2769 2568 185 2927 2692 895
1663 438 948 2124 941 1535
1385 2296 142 1627 2596 823
2276 449 1159 2900 1106 1160
1340 2837 3392 1871 2871 3815
684 37 2738 1273 823 3430
1172 2810 3627 1484 3037 4226
157 1314 2697 470 1693 2733
3378 3746 2353 4046 3903 3071
1565 1...

output:

20005

result:

ok single line: '20005'

Test #18:

score: 0
Accepted
time: 298ms
memory: 514036kb

input:

100 100
4335 5531 5978 6678 5584 6052
7082 1490 7056 7150 2511 9424
2273 5253 5295 3465 5987 6624
3303 840 1919 4871 2208 3858
6299 2059 7603 7334 5058 10001
1111 1108 38 2602 1127 1926
1331 7864 3878 3812 9408 5658
7589 6733 4164 8621 7366 7032
4018 7349 5179 6837 9267 5625
673 1827 6815 2692 4782 ...

output:

150281

result:

ok single line: '150281'

Test #19:

score: 0
Accepted
time: 252ms
memory: 511728kb

input:

100 100
1634 2473 9070 3110 2700 10740
5930 8629 797 7245 8803 1643
6651 264 6177 6938 334 6582
4474 4141 2419 6342 4865 3471
8865 9197 7159 9966 9865 8691
8184 6306 441 9586 8068 461
1196 3303 2148 2517 5265 2546
6774 9967 6882 7296 11043 7426
9528 1655 3789 11294 1944 4643
9505 5665 8672 10847 714...

output:

10784

result:

ok single line: '10784'

Test #20:

score: 0
Accepted
time: 274ms
memory: 512516kb

input:

100 100
2642 3587 1740 4626 6067 1907
1397 5929 8589 2787 7334 10980
6307 8094 9560 8707 10111 10420
5049 759 3875 7440 2650 6302
7186 4918 2350 8040 5436 3857
472 3591 2152 481 3605 3885
2043 6615 1776 2262 7903 2149
6177 7806 5627 7911 8454 8330
4845 6554 9231 7803 6710 11831
2378 1492 1672 2719 3...

output:

200461

result:

ok single line: '200461'

Test #21:

score: 0
Accepted
time: 278ms
memory: 513888kb

input:

100 100
5431 4014 8069 6303 6564 11468
8376 9580 5902 10131 10140 6206
6979 2414 6365 8121 6161 10312
3315 3054 2728 3407 6957 4387
7283 3281 3693 7756 3915 3870
1998 2997 7841 2863 4396 8716
4138 8824 3645 6172 10545 6118
9113 2716 2673 10655 6177 4247
5957 4056 742 8475 6476 2859
5195 6279 9437 80...

output:

375016

result:

ok single line: '375016'

Test #22:

score: 0
Accepted
time: 284ms
memory: 517204kb

input:

100 100
6439 5128 739 7819 7284 3635
7492 6879 3694 8322 9670 4543
2987 245 9748 4891 4939 13150
3891 9672 536 6507 10093 4218
5604 9001 8884 8829 13133 13036
7934 282 3199 9406 4581 5140
4984 2136 9626 5564 2535 10074
4869 6907 1417 7623 6940 5150
1274 2604 6184 3985 5891 10048
4421 2106 2436 9309 ...

output:

758581

result:

ok single line: '758581'

Test #23:

score: 0
Accepted
time: 286ms
memory: 511452kb

input:

100 100
790 259 2361 1826 996 3336
622 5473 7422 1749 5482 8102
2568 9306 1632 3279 10790 2787
11820 4608 12160 12743 5407 13740
8145 2582 1834 9700 3467 2987
9696 11525 4533 9813 12613 5951
8534 978 9912 9800 2023 10064
9396 13599 6238 9510 13795 7681
11654 1160 14474 12313 2318 15068
205 14961 549...

output:

180744

result:

ok single line: '180744'

Test #24:

score: 0
Accepted
time: 267ms
memory: 511304kb

input:

100 100
44594 67979 32342 45185 72760 36258
23073 28020 31507 27364 29255 35106
31193 40170 71145 31424 41997 73674
4525 68283 75412 8378 70144 77895
46154 44176 43211 48822 45402 45161
32151 31123 53633 34161 32467 56211
55921 79231 28885 60790 81211 31762
11579 2060 39332 11753 4146 41495
99266 30...

output:

2127983

result:

ok single line: '2127983'

Test #25:

score: 0
Accepted
time: 250ms
memory: 511476kb

input:

100 100
1301 81995 1501 1926 86255 4761
3361 50720 38475 11073 55509 38889
50693 30584 85825 55301 39531 86863
42795 52679 65831 44009 58092 70395
60073 19777 1096 65746 29461 6065
79481 38075 265 83008 47084 7844
78403 9015 24026 86008 11047 33992
60766 93230 51090 64202 98541 53627
33671 22112 892...

output:

3432066

result:

ok single line: '3432066'

Test #26:

score: 0
Accepted
time: 268ms
memory: 511732kb

input:

100 100
23317 60574 6841 36606 61692 13445
94297 61672 74060 113808 64924 93564
2709 66246 12591 3192 82736 14892
43946 45916 48743 62560 58366 49353
363 71218 95126 11541 72251 114399
84058 92645 10981 86799 109807 16339
87392 31992 39634 106793 43027 43549
35925 25259 52227 47785 43361 56729
657 3...

output:

73311271

result:

ok single line: '73311271'

Test #27:

score: 0
Accepted
time: 278ms
memory: 511376kb

input:

100 100
92188 254710 546692 189923 344842 607713
591614 429921 318069 671785 476928 408936
484552 760823 287873 582142 789005 379488
262209 78813 768734 309160 144384 840078
862989 52343 199927 877401 69149 264815
39779 760858 115728 129715 769123 165369
498156 390272 504585 593450 407122 566612
592...

output:

348819345

result:

ok single line: '348819345'

Test #28:

score: 0
Accepted
time: 283ms
memory: 511220kb

input:

1 2
0 0 0 1 1 100000
0 0 0 x+ y+
0 0 2 x- z+

output:

400000

result:

ok single line: '400000'

Test #29:

score: 0
Accepted
time: 237ms
memory: 511124kb

input:

100 2
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 107 107 108 108 108
107 10...

output:

1

result:

ok single line: '1'

Test #30:

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

input:

1 99
0 0 0 50 50 50
0 0 0 z- y+
1 0 0 z- y+
2 0 0 z- y+
3 0 0 z- y+
4 0 0 z- y+
5 0 0 z- y+
6 0 0 z- y+
7 0 0 z- y+
8 0 0 z- y+
9 0 0 z- y+
10 0 0 z- y+
11 0 0 z- y+
12 0 0 z- y+
13 0 0 z- y+
14 0 0 z- y+
15 0 0 z- y+
16 0 0 z- y+
17 0 0 z- y+
18 0 0 z- y+
19 0 0 z- y+
20 0 0 z- y+
21 0 0 z- y+
22 0...

output:

100

result:

ok single line: '100'

Test #31:

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

input:

1 2
0 0 0 100000 99998 99997
0 0 0 x- y+
0 0 2 x- z+

output:

79997500015

result:

ok single line: '79997500015'

Test #32:

score: 0
Accepted
time: 272ms
memory: 511368kb

input:

100 2
100 100 0 101 101 200
99 99 1 102 102 199
98 98 2 103 103 198
97 97 3 104 104 197
96 96 4 105 105 196
95 95 5 106 106 195
94 94 6 107 107 194
93 93 7 108 108 193
92 92 8 109 109 192
91 91 9 110 110 191
90 90 10 111 111 190
89 89 11 112 112 189
88 88 12 113 113 188
87 87 13 114 114 187
86 86 14...

output:

398

result:

ok single line: '398'

Test #33:

score: 0
Accepted
time: 283ms
memory: 511272kb

input:

100 2
2 0 0 3 3 3
4 0 0 5 3 3
6 0 0 7 3 3
8 0 0 9 3 3
10 0 0 11 3 3
12 0 0 13 3 3
14 0 0 15 3 3
16 0 0 17 3 3
18 0 0 19 3 3
20 0 0 21 3 3
22 0 0 23 3 3
24 0 0 25 3 3
26 0 0 27 3 3
28 0 0 29 3 3
30 0 0 31 3 3
32 0 0 33 3 3
34 0 0 35 3 3
36 0 0 37 3 3
38 0 0 39 3 3
40 0 0 41 3 3
42 0 0 43 3 3
44 0 0 4...

output:

398

result:

ok single line: '398'

Test #34:

score: 0
Accepted
time: 277ms
memory: 511264kb

input:

100 2
2 0 0 3 100000 100000
4 0 0 5 100000 100000
6 0 0 7 100000 100000
8 0 0 9 100000 100000
10 0 0 11 100000 100000
12 0 0 13 100000 100000
14 0 0 15 100000 100000
16 0 0 17 100000 100000
18 0 0 19 100000 100000
20 0 0 21 100000 100000
22 0 0 23 100000 100000
24 0 0 25 100000 100000
26 0 0 27 1000...

output:

19800203

result:

ok single line: '19800203'

Test #35:

score: 0
Accepted
time: 256ms
memory: 511368kb

input:

100 2
1000 0 0 1001 100000 99999
2000 0 0 2001 100000 99999
3000 0 0 3001 100000 99999
4000 0 0 4001 100000 99999
5000 0 0 5001 100000 99999
6000 0 0 6001 100000 99999
7000 0 0 7001 100000 99999
8000 0 0 8001 100000 99999
9000 0 0 9001 100000 99999
10000 0 0 10001 100000 99999
11000 0 0 11001 100000...

output:

179792640035239

result:

ok single line: '179792640035239'

Test #36:

score: 0
Accepted
time: 260ms
memory: 511264kb

input:

100 2
1000 0 0 1001 100000 99999
2000 0 0 2001 100000 99999
3000 0 0 3001 100000 99999
4000 0 0 4001 100000 99999
5000 0 0 5001 100000 99999
6000 0 0 6001 100000 99999
7000 0 0 7001 100000 99999
8000 0 0 8001 100000 99999
9000 0 0 9001 100000 99999
10000 0 0 10001 100000 99999
11000 0 0 11001 100000...

output:

ok

result:

ok single line: 'ok'

Test #37:

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

input:

5 4
1 1 1 3 2 2
1 2 2 3 3 3
1 3 3 3 4 4
1 4 4 3 5 5
1 5 5 3 6 6
1 3 3 z+ y-
1 3 3 z+ y+
2 3 3 z+ y-
2 4 4 y- z+

output:

0

result:

ok single line: '0'

Test #38:

score: 0
Accepted
time: 236ms
memory: 511200kb

input:

5 4
1 1 1 4 2 2
1 2 2 4 3 3
1 3 3 4 4 4
1 4 4 4 5 5
1 5 5 4 6 6
1 3 3 z+ y-
1 4 4 z+ y+
2 3 3 z+ y-
3 4 4 y- z+

output:

9

result:

ok single line: '9'

Test #39:

score: 0
Accepted
time: 218ms
memory: 511172kb

input:

5 4
1 1 1 3 2 2
1 2 2 3 3 3
1 3 3 6 4 4
0 4 4 5 5 5
1 5 5 3 6 6
1 3 3 y- z-
1 4 4 y- z+
2 3 3 y- x-
0 4 4 y- x+

output:

9

result:

ok single line: '9'

Test #40:

score: 0
Accepted
time: 256ms
memory: 511160kb

input:

11 21
1 1 5 2 2 6
2 2 5 3 3 6
3 3 5 4 4 6
2 4 5 3 5 6
1 5 5 2 6 6
2 6 0 3 7 999998
3 7 5 4 8 6
2 8 5 3 9 6
3 9 5 4 10 6
4 10 5 5 11 6
3 11 5 4 12 6
1 1 5 x+ y+
2 6 4 x- z+
2 6 6 x- z+
2 6 7 x- z+
2 6 8 x- z+
2 6 9 x- z+
2 6 10 x- z+
2 6 11 x- z+
2 6 12 x- z+
2 6 13 x- z+
2 6 14 x- z+
2 6 25 y+ z+
2 ...

output:

ok

result:

ok single line: 'ok'

Test #41:

score: 0
Accepted
time: 216ms
memory: 511184kb

input:

11 22
1 1 5 2 2 6
2 2 5 3 3 6
3 3 5 4 4 6
2 4 5 3 5 6
1 5 5 2 6 6
2 6 0 3 7 999998
3 7 5 4 8 6
2 8 5 3 9 6
3 9 5 4 10 6
4 10 5 5 11 6
3 11 5 4 12 6
1 1 5 x+ y+
2 6 4 x- z+
2 6 6 x- z+
2 6 7 x- z+
2 6 8 x- z+
2 6 9 x- z+
2 6 10 x- z+
2 6 11 x- z+
2 6 12 x- z+
2 6 13 x- z+
2 6 14 x- z+
2 6 25 y+ z+
2 ...

output:

3999961

result:

ok single line: '3999961'