QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200806#5123. Streets275307894aTL 1994ms12676kbC++143.1kb2023-10-04 20:27:042023-10-04 20:27:05

Judging History

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

  • [2023-10-04 20:27:05]
  • 评测
  • 测评结果:TL
  • 用时:1994ms
  • 内存:12676kb
  • [2023-10-04 20:27:04]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e5+5,M=2.1e4+5,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,T,A[N],B[N],f[N];
pii X[N],Y[N];int Xh,Yh;
int fa[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
vector<int> S[N];int pre[N];
ll C;
ll dd(ll x,ll y){return (x+y-1)/y;}
void Add(int x,int ti){
	int y=GF(x-1);if(!y) return;
	if(1ll*X[x].se*X[y].fi>=1ll*X[y].se*X[x].fi) return;
	ll w=dd(C*X[x].fi-C*X[y].fi,1ll*X[y].se*X[x].fi-1ll*X[x].se*X[y].fi);
	if(w>Y[Yh].fi) return;
	/*if((C-1ll*w*X[x].se)*1.0/X[x].fi+eps<(C-1ll*w*X[y].se)*1.0/X[y].fi){
		cerr<<w<<'\n';
		cerr<<X[x].se<<' '<<X[x].fi<<' '<<X[y].se<<' '<<X[y].fi<<' '<<C<<'\n';
		printf("%.10lf %.10lf\n",(C-1ll*w*X[x].se)*1.0/X[x].fi,(C-1ll*w*X[y].se)*1.0/X[y].fi);
	}
	assert((C-1ll*w*X[x].se)*X[y].fi>=(C-1ll*w*X[y].se)*X[x].fi);*/
	S[pre[w]].emplace_back(x);assert(pre[w]>=ti);
}
void Solve(){
	int i,j;scanf("%d%d%d",&n,&m,&T);
	for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);
	Me(f,0x3f);for(i=1;i<=n;i++) for(j=i;j<=n;j++) f[A[j]-A[i]]=min(f[A[j]-A[i]],B[i]+B[j]);
	for(i=1;i<=1e5;i++) if(f[i]<=1e8) X[++Xh]=make_pair(i,f[i]);
	for(i=1;i<=m;i++) scanf("%d",&A[i]);for(i=1;i<=m;i++) scanf("%d",&B[i]);
	Me(f,0x3f);for(i=1;i<=m;i++) for(j=i;j<=m;j++) f[A[j]-A[i]]=min(f[A[j]-A[i]],B[i]+B[j]);
	for(i=1;i<=1e5;i++) if(f[i]<=1e8) Y[++Yh]=make_pair(i,f[i]);
	cerr<<Xh<<' '<<Yh<<'\n';
	for(i=1;i<=Yh;i++) fill(pre+Y[i-1].fi+1,pre+Y[i].fi+1,i);
	while(T--){
		scanf("%lld",&C);ll ans=0;
		iota(fa+1,fa+Xh+1,1);for(i=1;i<=Yh;i++) S[i].clear();
		for(i=2;i<=Xh;i++) Add(i,0);
		for(i=1;i<=Yh;i++) {
			for(int j=0;j<S[i].size();j++){
				int p=S[i][j];if(fa[p]^p) continue;
				int y=GF(p-1);if(!y) continue;
				if((C-1ll*Y[i].fi*X[y].se)*X[p].fi>(C-1ll*Y[i].fi*X[p].se)*X[y].fi) continue;
				fa[y]=y-1;Add(p,i);
			}
			int l=0,r=Xh+1,mid;
			db p=-1e18;
			/*int x=GF(Xh);while(x){
				if((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+1<p){
					printf("%lf %lf\n",(C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+eps,p);
				}
				//assert((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+1>=p);
				p=(C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi;//printf("%.9lf ",p);
				if((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi>=Y[i].se) ans=max(ans,1ll*Y[i].fi*X[x].fi);
				x=GF(x-1);
			}*/
			while(l+1<r)  mid=l+r>>1,(!GF(mid)||C-1ll*Y[i].fi*X[GF(mid)].se>=1ll*X[GF(mid)].fi*Y[i].se?l:r)=mid;
			if(GF(l)) ans=max(ans,1ll*Y[i].fi*X[GF(l)].fi)/*,cerr<<Y[i].fi<<' '<<X[GF(l)].fi<<'\n'*/;
		}
		printf("%lld\n",ans);
		// if(T==80) exit(0);
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8572kb

input:

3 4 20
1 3 4
3 1 2
1 3 4 7
4 2 1 2
1
5
6
7
9
10
11
12
15
16
17
22
23
28
30
35
43
47
49
57

output:

0
0
1
1
1
2
2
3
3
4
4
6
6
9
9
12
12
12
18
18

result:

ok 20 numbers

Test #2:

score: 0
Accepted
time: 1990ms
memory: 11992kb

input:

4995 4998 100
4 7 20 34 44 100 102 130 175 198 205 250 257 259 267 278 300 324 337 346 353 364 403 427 439 440 451 523 532 534 555 599 634 639 756 802 805 825 855 859 890 905 912 915 953 989 1014 1031 1052 1059 1097 1124 1183 1216 1297 1308 1337 1342 1361 1392 1400 1421 1451 1471 1523 1537 1542 1619...

output:

9991201920
9941157660
8387550150
9892186440
9803600290
9986903784
9928424616
9892186440
9831470090
9768930402
9831470090
9058876564
9803600290
9857548260
9944740920
9892186440
9885418060
9831470090
9857548260
9768930402
8671693002
9803600290
9911595765
9058876564
9803600290
9838238470
9024072106
980...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 1994ms
memory: 12676kb

input:

4995 4996 100
72 80 119 144 216 272 283 292 300 313 317 332 337 338 369 374 416 422 447 480 506 535 571 581 590 592 604 614 622 639 676 677 691 695 700 723 739 742 748 755 779 787 797 839 847 856 864 878 886 888 890 894 898 899 904 1007 1023 1049 1051 1061 1070 1122 1125 1153 1168 1187 1190 1225 124...

output:

9985005184
9855576720
9855576720
6122924640
9437544131
9627630660
9951648960
9627630660
9635613716
9855576720
9855576720
9627630660
9936899280
9960518700
9254863411
9855576720
9936899280
9974416128
9941882280
7314670570
9984905280
9254274235
9818294436
9855576720
9945769020
9985005184
9855576720
981...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 1950ms
memory: 12284kb

input:

4999 4998 100
24 28 58 91 107 122 129 134 137 166 200 216 248 266 329 336 362 389 392 399 404 419 547 557 564 573 642 680 682 720 727 728 824 826 853 861 865 897 901 902 908 911 932 953 956 962 977 982 997 1002 1022 1025 1035 1062 1068 1085 1120 1168 1172 1192 1198 1205 1274 1294 1371 1372 1373 1410...

output:

9991701692
9253373820
9755390874
9968222577
9377310990
9829353624
9804851874
8890538665
9949256772
9253373820
9110273475
9377310990
8890538665
9794940174
9962335026
9444281184
9514977448
9708304002
9110273475
9377310990
8890538665
9253373820
9175336560
9664890422
6123991927
9621153720
9377310990
988...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 1987ms
memory: 11816kb

input:

4995 4999 100
15 43 47 59 95 107 176 180 264 328 338 362 367 369 373 391 428 484 502 550 573 577 596 614 621 628 649 676 678 702 705 715 748 755 764 779 800 805 842 846 854 858 888 909 928 946 998 1018 1036 1082 1084 1087 1093 1102 1113 1120 1128 1137 1160 1164 1173 1200 1241 1251 1260 1269 1298 130...

output:

9990601368
9839407611
9955914580
9634428612
9910930780
9843029676
9790830072
9790830072
9821886558
9921626928
7879145340
9944418720
9929496720
9987203312
9895336396
9880488046
9843029676
9821886558
9928824336
7899488010
9821886558
9910930780
9821886558
9988802736
9854913855
9929496720
9889812895
966...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 1956ms
memory: 12076kb

input:

4997 4999 100
45 46 51 93 99 135 140 144 186 189 206 229 231 232 246 251 267 275 297 364 395 466 474 486 489 504 558 559 571 591 599 623 632 645 646 732 740 749 753 780 781 870 904 920 954 956 971 983 984 1010 1022 1040 1045 1085 1108 1122 1129 1164 1210 1215 1243 1245 1262 1307 1317 1371 1425 1472 ...

output:

9989602700
8899349230
9798172153
9798172153
9905126028
9481804741
9798172153
9687737143
9595807459
9905126028
9671520110
9905126028
9798172153
9809016672
9706242469
9900946356
9938085284
9798172153
9798172153
1563896
8998119272
8899349230
9798172153
9942765826
9595807459
9931099704
9931099704
990512...

result:

ok 100 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

4998 4999 100
15 16 27 35 48 49 58 69 104 110 137 187 203 219 306 338 349 362 382 429 465 475 477 548 549 586 631 674 691 712 730 794 813 831 859 874 953 975 981 988 994 1027 1034 1048 1075 1084 1106 1108 1127 1134 1138 1140 1194 1223 1231 1237 1243 1252 1312 1337 1340 1343 1351 1359 1373 1419 1444 ...

output:

9987202871
322360992
34221228
170018460
2077200000
367788248
1849331484
104562900
130121250
667780755
14502428
199090845
70810920
229443360
34962225
732300000
593392380
465415095
179545680
11473369
765100000
952200000
10389199
489931907
1478004636
95030900
377990696
144950880
621853944
400045988
820...

result: