QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410451#8648. TowerRafi2238 15ms4120kbC++141.6kb2024-05-14 01:02:382024-05-14 01:02:38

Judging History

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

  • [2024-05-14 01:02:38]
  • 评测
  • 测评结果:38
  • 用时:15ms
  • 内存:4120kb
  • [2024-05-14 01:02:38]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=2007;

ll l[N],r[N];
vector<pair<ll,int>>Q[N];
ll mn[2*N],mx[2*N];
ll X[N];
ll d;

bool inside(ll l,ll r,ll x)
{
	return l+(x-l%d+d)%d<=r;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    ll a,b;
    cin>>n>>q>>d>>a>>b;
    vector<pair<ll,int>>V;
    for(int i=1;i<=n;i++)
    {
		cin>>l[i]>>r[i];
		if(r[i]+1>=d) V.pb({r[i]+1-d,i});
	}
    for(int i=1;i<=n+q;i++)
    {
		mn[i]=infl;
		mx[i]=-infl;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>X[i];
		V.pb({X[i],i+n});
	}
	sort(all(V));
	int j=0;
	for(auto [x,i]:V)
	{
		while(j<n&&x>r[j+1]) j++;
		if(j==n||x<l[j+1]) Q[j].pb({x,i});
	}
	r[0]=-1;
	for(int i=0;i<=n;i++)
	{
		if(i>0)
		{
			mn[i]++;
			mx[i]++;
		}
		for(int j=i;j<=n;j++)
		{
			if(inside(l[j],r[j],(r[i]+1)%d)) break;
			for(auto [x,k]:Q[j])
			{
				if(inside(r[j]+1,x,(r[i]+1)%d))
				{
					mn[k]=min(mn[k],mn[i]+(r[j]+1-(r[i]+1)+d-1)/d);
					mx[k]=max(mx[k],mx[i]+(x-(r[i]+1))/d);
				}
			}
		}
	}
	for(int i=1;i<=q;i++)
	{
		if(mn[n+i]==infl) cout<<-1<<endl;
		else
		{
			ll w1=(X[i]-mn[n+i]*d)*a+b*mn[n+i];
			ll w2=(X[i]-mx[n+i]*d)*a+b*mx[n+i];
			cout<<min(w1,w2)<<endl;
		}
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

2000 200000
500 66309 387245
91 122
793 1029
1127 1131
1304 1611
2007 2039
2601 2701
2906 3052
3253 3263
3495 3609
4157 4225
4283 4283
4757 4766
4786 4847
4885 5086
5326 5342
5607 5750
5847 5877
6093 6230
6548 6793
7206 7308
7413 7419
7752 7780
8244 8410
8501 8515
9335 9447
9512 9514
9602 9906
10076...

output:


result:


Subtask #2:

score: 38
Accepted

Test #29:

score: 38
Accepted
time: 2ms
memory: 3832kb

input:

1938 1960
999999 47694 9291
2883622 3085639
3674880 3745876
9982198101 9982517489
19960889157 19960925795
19962228551 19962276101
19964301694 19964730442
19964826417 19965369252
19965984922 19966442459
19968019821 19968213820
19968334967 19968392242
19968426638 19968840337
19969017519 19969109591
19...

output:

2629532778036
1625568767553
-1
-1
-1
931487890158
217249154424
-1
3376854733974
453288498306
1144114552242
194772660096
116508067359
1965611506731
2806098123096
3404924462019
1737385084617
1649786307423
-1
3043407203193
2248403158668
-1
-1
538903132932
2740777563264
-1
3173320399527
-1
-1
2616652920...

result:

ok 1960 lines

Test #30:

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

input:

1837 1989
999999 41963 54422
9980315942 9981214568
9981614247 9981843710
9982430252 9982433585
9983182843 9983561789
9984404759 9984499318
9984655332 9984859904
9985420428 9985717345
9985762820 9985867258
9986396224 9986498679
9986533284 9986947589
9987502488 9988096750
9989096806 9989207060
9989676...

output:

-1
2554711024271
-1
977926019067
3238028322568
201257084557
-1
3205448836431
387280383252
-1
-1
-1
1216454626736
823964810173
117884656882
2669122054316
734561443433
1448900485845
3203724783289
796733108264
883217412007
-1
-1
147443422287
2027763666999
2378863303928
-1
-1
3091310739595
2261110540233...

result:

ok 1989 lines

Test #31:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

1985 1968
999999 1 1000000
9978505229 9979247763
9979301501 9979397117
9981449577 9981533536
9981765886 9982271507
9983158890 9983349521
9983843213 9984416208
9985032631 9985197994
9987158017 9987185683
9987259105 9988030168
9988487256 9988529335
9988581372 9988946469
9989439295 9989530721
998958116...

output:

-1
-1
700140493470
-1
489978355522
300086770672
-1
559982430287
130003223151
640114158260
450000487914
740106557204
29952519876
-1
240105075210
350026198844
170023233424
-1
700129344373
559996047761
29958778074
-1
519963146983
489976670882
610079022591
80061443986
479963278603
39959493320
1399929819...

result:

ok 1968 lines

Test #32:

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

input:

1879 1909
999999 1 1000000
460689 754731
2693364 2905962
3319681 3325104
3801465 3977535
4035457 4085070
5277090 5364349
9984311172 9984412612
9985376085 9985569458
9987260530 9987358997
19966359490 19966462743
19967267902 19967747838
19968440841 19968684937
19968871698 19969057992
19969415495 19969...

output:

479861899804
479818936396
-1
819788300403
669700939937
80006774552
-1
769777335986
869739454474
619739632941
509845128160
269956484712
919935604516
269952659247
399861650164
879829770503
40026405880
-1
-1
809756094408
130027392164
-1
449835037240
-1
190003318228
-1
30001962211
499837013487
300212407...

result:

ok 1909 lines

Test #33:

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

input:

1940 1824
999999 1 999999
9978317553 9978682456
9978688516 9978878611
9978916901 9978998453
9979512428 9980182210
9982686148 9982981767
9983520680 9984134501
9987258775 9987376861
9990965623 9991023044
9993014239 9993353245
9993498632 9993507872
9994237367 9994421501
9995634031 9996033703
9996546527...

output:

110138183242
539977719961
290029467104
200095116550
749939262424
529972467394
-1
-1
780021180799
749957388309
60012891726
-1
110139276095
860055290897
749957559179
699950438736
300066809495
-1
260070941533
230083391036
300028601356
-1
370090142336
100123227398
749913884611
100065909438
230087376207
...

result:

ok 1824 lines

Test #34:

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

input:

2000 2000
2000 72242 918440
3502 3628
3917 4295
4835 6269
8954 9053
9391 9498
9539 10488
12030 12437
12939 13001
14484 14661
21293 22714
23496 23948
24054 24123
24442 24452
25204 25888
25990 26335
27891 29357
30247 30614
32576 32787
34652 34700
34808 35396
35720 35728
35747 35836
39325 39535
40111 4...

output:

-1
-1
-1
41331109907612
-1
-1
-1
-1
-1
-1
41331302679640
-1
-1
105623453414058
-1
64292666451688
-1
146954757408300
-1
40888972
27554456283342
-1
-1
-1
41331123604136
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
41331120817986
114808753616582
-1
-1
-1
78069463962690
78069497678998
-1
-1
229...

result:

ok 2000 lines

Test #35:

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

input:

2000 2000
2000 230 625018
277 787
895 1341
2149 3435
4136 4488
4642 5289
6460 6507
6514 7706
8903 9587
15877 16228
17893 18664
19210 20608
20764 21133
21815 22730
23907 24807
24879 25004
28142 28157
28639 28653
29234 29479
31122 31898
33500 33856
19999942795 19999943136
19999943507 19999943865
19999...

output:

25299964891184
-1
-1
73599989788774
-1
-1
-1
-1
-1
20699961474702
-1
-1
-1
-1
59799962174496
55199932107284
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
59799964050362
-1
-1
-1
-1
66699981671922
-1
-1
73599990803994
-1
27599955499472
-1
-1
-1
-1
55199944607118
-1
-1
22999956186730
78199996059730
-1
-1
-1
...

result:

ok 2000 lines

Test #36:

score: 0
Accepted
time: 2ms
memory: 3896kb

input:

2000 2000
2000 295 590000
3810 4650
5193 5314
6077 6161
7589 7846
9999962966 9999963017
9999965179 9999966334
9999969386 9999970813
19999926448 19999926573
19999927152 19999927755
19999929100 19999929729
19999930809 19999931622
19999932990 19999933019
19999933778 19999933917
19999934040 19999934345
...

output:

-1
-1
-1
61950044019900
29500018664060
-1
41300037658225
85550042906275
-1
-1
-1
-1
103250043467365
-1
103250032668890
-1
23600030858180
-1
-1
23600022766920
-1
-1
-1
-1
-1
-1
-1
64900035295275
-1
-1
76700043064985
-1
-1
-1
-1
-1
-1
-1
-1
76700014152035
-1
-1
-1
-1
-1
-1
73750024285580
-1
-1
-1
-1
5...

result:

ok 2000 lines

Test #37:

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

input:

2000 2000
1000000000 84022 860353
1569988396 1685009448
1782896103 2023925423
2743748189 3201999434
3348913628 3486693274
3586050490 3600384245
3829423794 3993187865
4079023827 4145323681
4801555373 5508268361
5580494464 5597647672
5662434819 6078038246
6113079134 6228562717
6277774595 6513373409
66...

output:

1699551771303243
-1
-1
-1
1077130449787194
-1
-1
-1
4213960752006101
-1
-1
3907605594392520
3462208157256638
-1
-1
-1
436818127827278
140063800902968
733152710849402
1524830249781496
-1
140199939796929
-1
3767755882701727
-1
-1
3219254988971477
-1
-1
3791754131769005
3787309355033107
216604035661138...

result:

ok 2000 lines

Test #38:

score: 0
Accepted
time: 2ms
memory: 4120kb

input:

2000 2000
1000000000 73351 798016
5379164 85948628
152114738 186910996
216089947 296297297
320601651 498439329
749737863 883048527
1017428051 1215354384
1500998319 1851811527
2035869094 2196064026
2289057708 2373716965
2419663795 2455077575
2600831714 2796612190
3737756045 3765767374
3963896915 4138...

output:

1352392662585144
-1
-1
275619944941055
494581361210771
-1
1906283000186755
-1
-1
631672883910142
2000127534373511
1067186609237468
2744520683341053
2587495002252512
-1
1150027859519700
2191930206191286
-1
2364534538759850
-1
-1
2319174164915293
-1
3122071296236563
-1
2707809817429526
150118726886524...

result:

ok 2000 lines

Test #39:

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

input:

2000 2000
1 11621 8066
100201834835 100201834835
100258958238 100258958238
100281167128 100281167128
100429123403 100429123403
100989550866 100989550866
101166447769 101166447769
102684659624 102684659624
102808801085 102808801085
102981197474 102981197474
103001829421 103001829421
103037865521 1030...

output:

-1
482407665890812
-1
-1
723597354250222
-1
-1
-1
-1
-1
-1
-1
634158842204382
-1
767149223586088
-1
320742329546098
313907157146068
442988049072114
400535162863556
-1
578773630434064
-1
690693072960138
433934921909614
781396623802876
599823436022858
169766199217980
119517605193712
548419539744340
-1...

result:

ok 2000 lines

Test #40:

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

input:

2000 2000
2 32886 78704
204643836 204643836
1113623028 1113623028
1135646654 1135646654
1959997357 1959997357
2040819163 2040819163
2061775595 2061775595
2464113849 2464113849
3478319937 3478319937
3779559895 3779559895
3849318319 3849318319
3959865089 3959865089
5012240362 5012240362
5588017105 558...

output:

2605361503242182
2620518620132540
-1
312761570833468
896240997173292
2686095482500068
1236321842423432
363842065334418
263528977919424
2485121231037864
1249828393110782
1562748331364332
2421388383381086
-1
-1
-1
-1
-1
-1
-1
686077868878886
1746971073564236
-1
-1
-1
966005157875456
2077496417864340
1...

result:

ok 2000 lines

Test #41:

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

input:

2000 2000
3 308586 925758
229941318 229941319
810862719 810862720
1381846176 1381846177
1967227686 1967227687
2176874215 2176874216
2860203229 2860203229
3449456731 3449456732
3511222605 3511222606
3734211059 3734211060
4013508856 4013508857
4662500353 4662500354
4698830876 4698830876
5193812601 519...

output:

629433234541116
11214604732761558
-1
683088725581566
-1
23919958255515348
2601147932894166
29865833510728218
26650435163928468
-1
-1
-1
8366307952517844
-1
18808177136118366
26539226966243934
5466347690884932
11182192870993692
19699683523191750
18937036704809076
-1
-1
-1
10491593943203292
9296394537...

result:

ok 2000 lines

Test #42:

score: 0
Accepted
time: 15ms
memory: 3844kb

input:

2000 2000
1000000000000 98903 356584
100068122467 100323582946
101034122653 101037471983
101192671139 101417983373
101752751591 102138275674
102743548699 102997923214
103040734538 103215955014
103257686114 103679787488
103779917169 103810888674
104044408487 104086239085
104254838840 104683673158
104...

output:

4881267912001978
758081698558947
-1
-1
2299457562076388
-1
6225377721117954
-1
-1
9313806889712353
374853586984842
-1
-1
5514185530543543
-1
2339590367909865
-1
-1
-1
-1
3794542741845079
-1
-1
-1
-1
-1
-1
4294906976234245
-1
2980394495846950
266788141953585
370001816054486
-1
1210592068888405
987787...

result:

ok 2000 lines

Test #43:

score: 0
Accepted
time: 15ms
memory: 3860kb

input:

2000 2000
1000000000000 56232 838675
100081867458 100242549128
101925831793 101996793761
102278462889 102363135838
102609220006 102653402499
102871255176 103007518598
103011266371 103308640763
103332053476 103370250699
103408334823 103732853154
103742708168 103829810047
104116698365 104427911390
104...

output:

-1
879346853108064
-1
-1
1346153229476352
1977095062998000
-1
2522316962185416
-1
2541388335030072
3662470967464584
2881580180742648
-1
-1
-1
-1
1783397370313152
-1
89495784869040
5233202865706464
2299192313090904
-1
-1
-1
4499236901922048
1906943270738616
-1
3108715042358376
2291198847693624
-1
-1
...

result:

ok 2000 lines

Subtask #3:

score: 0
Runtime Error

Test #44:

score: 0
Runtime Error

input:

198085 196577
999999 1 999999
562622 895604
1799586 1975565
2518299 2941986
4934097 5403130
5755102 5996130
6036200 6112534
6391882 6431514
6451793 6555786
6613625 6621089
7130933 7204522
7335426 7522555
7748545 7784568
8184979 8494887
9066856 9178094
9303615 9384897
9716200 9719420
11693951 1183563...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%