| Task: | Palembang Bridges |
| Sender: | Lieska |
| Submission time: | 2019-04-04 13:44:51 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | 31 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 8 |
| #2 | ACCEPTED | 14 |
| #3 | ACCEPTED | 9 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.01 s | 1, 2 | details |
| #2 | ACCEPTED | 0.02 s | 1, 2 | details |
| #3 | ACCEPTED | 0.02 s | 1, 2 | details |
| #4 | ACCEPTED | 0.02 s | 1, 2 | details |
| #5 | ACCEPTED | 0.02 s | 1, 2 | details |
| #6 | ACCEPTED | 0.03 s | 1, 2 | details |
| #7 | ACCEPTED | 0.02 s | 1, 2 | details |
| #8 | ACCEPTED | 0.02 s | 1, 2 | details |
| #9 | ACCEPTED | 0.02 s | 1, 2 | details |
| #10 | ACCEPTED | 0.02 s | 1, 2 | details |
| #11 | ACCEPTED | 0.01 s | 1, 2 | details |
| #12 | ACCEPTED | 0.12 s | 2 | details |
| #13 | ACCEPTED | 0.28 s | 2 | details |
| #14 | ACCEPTED | 0.21 s | 2 | details |
| #15 | ACCEPTED | 0.16 s | 2 | details |
| #16 | ACCEPTED | 0.18 s | 2 | details |
| #17 | ACCEPTED | 0.20 s | 2 | details |
| #18 | ACCEPTED | 0.19 s | 2 | details |
| #19 | ACCEPTED | 0.24 s | 2 | details |
| #20 | ACCEPTED | 0.17 s | 2 | details |
| #21 | ACCEPTED | 0.19 s | 2 | details |
| #22 | ACCEPTED | 0.01 s | 3, 4, 5 | details |
| #23 | ACCEPTED | 0.01 s | 3, 4, 5 | details |
| #24 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #25 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #26 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
| #27 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #28 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
| #29 | ACCEPTED | 0.04 s | 3, 4, 5 | details |
| #30 | ACCEPTED | 0.03 s | 3, 4, 5 | details |
| #31 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #32 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #33 | ACCEPTED | 0.02 s | 3, 4, 5 | details |
| #34 | ACCEPTED | 1.64 s | 4, 5 | details |
| #35 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #36 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #37 | ACCEPTED | 0.09 s | 4, 5 | details |
| #38 | ACCEPTED | 0.72 s | 4, 5 | details |
| #39 | ACCEPTED | 0.28 s | 4, 5 | details |
| #40 | ACCEPTED | 1.57 s | 4, 5 | details |
| #41 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #42 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #43 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #44 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #45 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #46 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #47 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #48 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #49 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #50 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #51 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #52 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #53 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #54 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #55 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #56 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #57 | TIME LIMIT EXCEEDED | -- | 5 | details |
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k, n, a, b, x, t[100001], r[100001], y, z, p[100001], w;
char c, c1;
multiset<ll> s;
int main(){
cin >> k >> n;
for (int i=1; i<=n; ++i){
cin >> c >> a >> c1 >> b;
x+=abs(b-a);
if (c!=c1){
if (a>b) swap(a,b);
t[i]=a;
r[i]=b;
p[i]=1;
s.insert(a);
s.insert(b);
y++;
x++;
}
}
if (k==1){
a=1;
auto it=s.begin();
while (a<=y){
a++;
it++;
}
a=*it;
for (int i=1; i<=n; ++i) {
if (p[i] && ((a<t[i] && a<r[i]) || (a>t[i]&& a>r[i]))) x+=2*(min(abs(t[i]-a),abs(r[i]-a)));
}
}
if (k==2){
w=1e18;
auto it=s.begin();
while (it!=s.end()){
auto ir=s.find(*it);
while (*ir==*it) ir++;
while (ir!=s.end()){
z=0;
a=*it;
b=*ir;
for (int i=1; i<=n; ++i) {
if (p[i]){
if (a>r[i]) z+=2*(a-r[i]);
else if (b<t[i]) z+=2*(t[i]-b);
else if (a<t[i] && b>r[i]) z+=2*(min(t[i]-a, b-r[i]));
}
}
if (z<w) w=z;
ir++;
}
it++;
}
}
if (w==1e18) cout << x;
else cout << x+w;
}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1 B 457748887 B 796098674 |
| correct output |
|---|
| 338349787 |
| user output |
|---|
| 338349787 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 4 B 90 B 72 A 68 A 90 A 15 A 42 A 45 A 15 |
| correct output |
|---|
| 97 |
| user output |
|---|
| 97 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 0 B 1 A 1 B 0 A 0 B 1 B 0 A 0 ... |
| correct output |
|---|
| 1969 |
| user output |
|---|
| 1969 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 598380 B 85785 B 458027 A 842152 B 107714 A 39933 B 814225 A 328927 ... |
| correct output |
|---|
| 497512790 |
| user output |
|---|
| 497512790 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 967 B 224488483 A 870079127 A 647780056 B 965306270 B 735321905 A 82275290 A 515414803 B 41707746 ... |
| correct output |
|---|
| 473798660797 |
| user output |
|---|
| 473798660797 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 1000000000 B 0 A 0 B 1000000000 B 0 A 1000000000 A 1000000000 B 0 ... |
| correct output |
|---|
| 1000000001000 |
| user output |
|---|
| 1000000001000 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 B 540773 A 324388 B 1033055 A 1254946 A 2804687 B 2012944 A 3827608 B 3200426 ... |
| correct output |
|---|
| 500006153353 |
| user output |
|---|
| 500006153353 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 1000000000 B 0 B 1 A 999999999 A 999999998 B 2 A 3 B 999999997 ... |
| correct output |
|---|
| 999999002000 |
| user output |
|---|
| 999999002000 |
Test 9
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 B 306275120 A 306275122 A 526391763 B 526391756 B 152153706 A 152153714 B 275942345 A 275942351 ... |
| correct output |
|---|
| 499047189554 |
| user output |
|---|
| 499047189554 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 0 B 0 A 500000000 B 500000000 A 1000000000 B 1000000000 B 1000000000 A 1000000000 ... |
| correct output |
|---|
| 656000001000 |
| user output |
|---|
| 656000001000 |
Test 11
Group: 1, 2
Verdict: ACCEPTED
| input |
|---|
| 1 1000 A 500000001 B 500000000 B 499999999 A 499999998 B 1000000000 A 999999999 A 999999997 B 999999998 ... |
| correct output |
|---|
| 650999816318 |
| user output |
|---|
| 650999816318 |
Test 12
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 A 1 B 1 B 1 A 0 A 0 B 1 A 0 B 0 ... |
| correct output |
|---|
| 199742 |
| user output |
|---|
| 199742 |
Test 13
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 B 197201502 A 236725324 B 921493373 A 697882177 A 353914239 B 965797962 A 619173343 B 76946356 ... |
| correct output |
|---|
| 49896622370502 |
| user output |
|---|
| 49896622370502 |
Test 14
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 89829 A 5656 B 4153 A 5854 B 8220 A 1115 B 5226 A 2446 B 3407 ... |
| correct output |
|---|
| 448956640 |
| user output |
|---|
| 448956640 |
Test 15
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 58906 B 262032447 A 615361070 B 110761024 A 66611392 A 720901527 B 757393905 A 602897217 B 978610640 ... |
| correct output |
|---|
| 29450986771481 |
| user output |
|---|
| 29450986771481 |
Test 16
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 A 0 B 1000000000 B 1000000000 A 0 B 0 A 1000000000 A 1000000000 B 0 ... |
| correct output |
|---|
| 100000000100000 |
| user output |
|---|
| 100000000100000 |
Test 17
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 A 7461 B 9756 A 12548 B 14001 A 26302 B 21823 A 32953 B 37935 ... |
| correct output |
|---|
| 50000000610462 |
| user output |
|---|
| 50000000610462 |
Test 18
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 B 0 A 1000000000 A 1 B 999999999 B 2 A 999999998 B 999999997 A 3 ... |
| correct output |
|---|
| 99990000200000 |
| user output |
|---|
| 99990000200000 |
Test 19
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 B 400220047 A 400220048 A 14044122 B 14044122 A 45270242 B 45270245 B 994675758 A 994675758 ... |
| correct output |
|---|
| 50093795762125 |
| user output |
|---|
| 50093795762125 |
Test 20
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 B 1000000000 A 1000000000 A 500000000 B 500000000 B 1000000000 A 1000000000 A 0 B 0 ... |
| correct output |
|---|
| 66718000100000 |
| user output |
|---|
| 66718000100000 |
Test 21
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1 100000 A 1 B 0 A 2 B 3 A 5 B 4 B 500000000 A 500000001 ... |
| correct output |
|---|
| 66771748924060 |
| user output |
|---|
| 66771748924060 |
Test 22
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 1 B 686779001 B 298011277 |
| correct output |
|---|
| 388767724 |
| user output |
|---|
| 388767724 |
Test 23
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 4 B 85 B 16 A 88 A 72 A 13 A 8 B 5 B 68 |
| correct output |
|---|
| 153 |
| user output |
|---|
| 153 |
Test 24
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 B 1 A 1 B 1 A 1 B 0 A 1 B 0 A 1 ... |
| correct output |
|---|
| 135 |
| user output |
|---|
| 135 |
Test 25
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 A 80895559 B 504694055 A 550515244 B 637123084 A 824581457 B 293902519 A 65276676 B 906746170 ... |
| correct output |
|---|
| 39400461569 |
| user output |
|---|
| 39400461569 |
Test 26
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 61 A 882469 B 477162 A 276781 B 782546 B 696587 A 81196 B 573379 A 354344 ... |
| correct output |
|---|
| 23533490 |
| user output |
|---|
| 23533490 |
Test 27
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 24 B 246060972 B 745635077 A 805134171 A 471810707 B 252217199 B 377725124 B 793449133 B 882787637 ... |
| correct output |
|---|
| 7222227740 |
| user output |
|---|
| 7222227740 |
Test 28
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 A 0 B 1000000000 B 1000000000 A 0 B 1000000000 A 0 B 1000000000 A 0 ... |
| correct output |
|---|
| 100000000100 |
| user output |
|---|
| 100000000100 |
Test 29
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 B 7277035 A 2363507 A 14481349 B 18074096 A 23772733 B 25361815 B 38014142 A 39221304 ... |
| correct output |
|---|
| 25052929066 |
| user output |
|---|
| 25052929066 |
Test 30
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 A 0 B 1000000000 A 1 B 999999999 B 999999998 A 2 B 3 A 999999997 ... |
| correct output |
|---|
| 99999990200 |
| user output |
|---|
| 99999990200 |
Test 31
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 B 229133622 A 229133615 A 286436586 B 286436582 A 177918170 B 177918177 A 928539152 B 928539147 ... |
| correct output |
|---|
| 25763506210 |
| user output |
|---|
| 25763506210 |
Test 32
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 B 1000000000 A 1000000000 B 1000000000 A 1000000000 B 500000000 A 500000000 B 0 A 0 ... |
| correct output |
|---|
| 30000000100 |
| user output |
|---|
| 30000000100 |
Test 33
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 100 B 1 A 0 A 500000000 B 500000001 A 3 B 2 B 999999999 A 1000000000 ... |
| correct output |
|---|
| 30000000838 |
| user output |
|---|
| 30000000838 |
Test 34
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 1000 B 1 A 0 A 0 B 0 B 1 B 1 B 1 A 1 ... |
| correct output |
|---|
| 1488 |
| user output |
|---|
| 1488 |
Test 35
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 A 55 B 99 A 49 B 36 B 56 A 43 B 30 A 21 ... |
| correct output |
|---|
| 40742 |
| user output |
|---|
| (empty) |
Test 36
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 993 B 856945560 A 98103483 B 25758143 A 606399727 B 765461653 A 689513816 A 880180326 B 997125325 ... |
| correct output |
|---|
| 379585137648 |
| user output |
|---|
| (empty) |
Test 37
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 328 A 0 B 0 B 0 A 1 B 1 A 1 A 1 B 1 ... |
| correct output |
|---|
| 475 |
| user output |
|---|
| 475 |
Test 38
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 543 A 84 B 67 B 8 A 52 A 71 B 4 A 37 B 4 ... |
| correct output |
|---|
| 20775 |
| user output |
|---|
| 20775 |
Test 39
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 385 A 286133 B 305048 B 3019 A 211390 A 680205 B 943092 A 717521 B 2626 ... |
| correct output |
|---|
| 150638388 |
| user output |
|---|
| 150638388 |
Test 40
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 1000 A 1000000000 B 0 B 0 A 1000000000 B 1000000000 A 0 B 0 A 1000000000 ... |
| correct output |
|---|
| 1000000001000 |
| user output |
|---|
| 1000000001000 |
Test 41
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 A 337683 B 154786 A 1080479 B 1653867 A 2096703 B 2014255 A 3269807 B 3378028 ... |
| correct output |
|---|
| 250005306826 |
| user output |
|---|
| (empty) |
Test 42
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 B 0 A 1000000000 A 1 B 999999999 A 2 B 999999998 B 999999997 A 3 ... |
| correct output |
|---|
| 999999002000 |
| user output |
|---|
| (empty) |
Test 43
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 B 487537672 A 487537682 A 702434952 B 702434943 A 924937477 B 924937478 A 438742511 B 438742503 ... |
| correct output |
|---|
| 248460366924 |
| user output |
|---|
| (empty) |
Test 44
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 B 500000000 A 500000000 A 0 B 0 B 0 A 0 A 1000000000 B 1000000000 ... |
| correct output |
|---|
| 323000001000 |
| user output |
|---|
| (empty) |
Test 45
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 1000 B 0 A 1 A 500000001 B 500000000 A 500000003 B 500000002 A 499999996 B 499999997 ... |
| correct output |
|---|
| 328999889746 |
| user output |
|---|
| (empty) |
Test 46
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 1 B 0 A 0 B 1 A 1 B 1 B 0 A 0 ... |
| correct output |
|---|
| 150253 |
| user output |
|---|
| (empty) |
Test 47
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 57 B 62 A 81 B 84 A 29 B 62 B 84 A 93 ... |
| correct output |
|---|
| 4054233 |
| user output |
|---|
| (empty) |
Test 48
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 B 376633 A 401436 B 929991 A 301184 A 594140 B 788956 A 269074 B 579617 ... |
| correct output |
|---|
| 39017925999 |
| user output |
|---|
| (empty) |
Test 49
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 B 957291126 A 804724561 B 643453098 A 837804172 A 968031915 B 244064467 B 806058719 A 777366893 ... |
| correct output |
|---|
| 39023916424909 |
| user output |
|---|
| (empty) |
Test 50
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 765748723 B 736102973 B 30767265 A 892885151 A 438782247 B 603304522 B 556204289 A 731709903 ... |
| correct output |
|---|
| 39003712943872 |
| user output |
|---|
| (empty) |
Test 51
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 52924 B 214946095 A 74195083 B 144150299 A 848919272 A 632662655 B 429803598 B 132419689 A 911407267 ... |
| correct output |
|---|
| 20674441803953 |
| user output |
|---|
| (empty) |
Test 52
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 B 1000000000 A 0 B 0 A 1000000000 B 1000000000 A 0 A 0 B 1000000000 ... |
| correct output |
|---|
| 100000000100000 |
| user output |
|---|
| (empty) |
Test 53
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 9838 B 2205 A 15278 B 17118 A 25088 B 22794 B 31319 A 39536 ... |
| correct output |
|---|
| 25000001294215 |
| user output |
|---|
| (empty) |
Test 54
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 0 B 1000000000 A 1 B 999999999 A 2 B 999999998 A 999999997 B 3 ... |
| correct output |
|---|
| 99990000200000 |
| user output |
|---|
| (empty) |
Test 55
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 B 69772706 A 69772713 A 701457803 B 701457802 B 526650518 A 526650528 B 44276587 A 44276586 ... |
| correct output |
|---|
| 25049824938170 |
| user output |
|---|
| (empty) |
Test 56
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 A 0 B 0 A 500000000 B 500000000 B 0 A 0 A 0 B 0 ... |
| correct output |
|---|
| 33071000100000 |
| user output |
|---|
| (empty) |
Test 57
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2 100000 B 999999999 A 1000000000 A 0 B 1 B 500000001 A 500000000 B 2 A 3 ... |
| correct output |
|---|
| 33278897746546 |
| user output |
|---|
| (empty) |