QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#410451 | #8648. Tower | Rafi22 | 38 | 15ms | 4120kb | C++14 | 1.6kb | 2024-05-14 01:02:38 | 2024-05-14 01:02:38 |
Judging History
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;
}
详细
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%