oj.uz

Submission #500304

# Submission time Handle Problem Language Result Execution time Memory
500304 2021-12-30T16:47:52 Z beaconmc Palembang Bridges (APIO15_bridge) C++14
100 / 100
 442 ms 21412 KB 
#include <bits/stdc++.h>

typedef long long ll;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>

ll addlater;
vector<vector<ll> > tings;
ordered_set sustree;
ll rsum, lsum;
ll median, nextmed;
bool cmp(vector<ll> a, vector<ll> b) { return a[0] + a[1] < b[0] + b[1]; };

void insert(ll a, ll b){
    if (a>b) swap(a,b);
    if (sustree.size() !=0) median = *sustree.find_by_order(sustree.size()/2 - 1), nextmed = *sustree.find_by_order(sustree.size()/2);
    else median = a, nextmed = b; 
    

    if (a<=median && b>median) lsum += a, rsum += b;

    else if (a<=median && b<=median) lsum += a+b-median, rsum += median;

    else {
        sustree.insert(a); sustree.insert(b);
        median = *sustree.find_by_order(sustree.size()/2 - 1);
        lsum += median, rsum += a+b-median;
        goto skip;
    }

    sustree.insert(a); sustree.insert(b);
    skip:;
}

int main(){
    ll k, n;
    cin.tie(0)->sync_with_stdio(0);
    cin >> k >> n;
    FOR(i,0,n){
        char a,b;
        ll x,y;
        cin >> a >> x >> b >> y;

        if (a==b) addlater += abs(x-y);
        else tings.push_back({x,y});
    }
    n = tings.size();

    addlater += n;

    ll prefs[100001];

    sort(tings.begin(), tings.end(), cmp);
    rsum = 0; lsum = 0;

    FOR(i,0,n){
        insert(tings[i][0], tings[i][1]);
        prefs[i] = rsum - lsum;
    }
    ll ans = prefs[n-1];

    if (k==2){
        sustree.clear();
        rsum = 0; lsum = 0;
        FORNEG(i, n-1, 0){
            insert(tings[i][0], tings[i][1]);
            ans = min(ans, rsum - lsum + prefs[i-1]);
        }
    }
    cout << ans + addlater;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 2 ms 1232 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 2 ms 1228 KB Output is correct
9 Correct 3 ms 1228 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 2 ms 1228 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 1088 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 2 ms 1268 KB Output is correct
6 Correct 2 ms 1244 KB Output is correct
7 Correct 3 ms 1228 KB Output is correct
8 Correct 2 ms 1228 KB Output is correct
9 Correct 3 ms 1228 KB Output is correct
10 Correct 2 ms 1232 KB Output is correct
11 Correct 2 ms 1228 KB Output is correct
12 Correct 235 ms 19960 KB Output is correct
13 Correct 277 ms 21412 KB Output is correct
14 Correct 218 ms 18356 KB Output is correct
15 Correct 152 ms 13264 KB Output is correct
16 Correct 302 ms 20676 KB Output is correct
17 Correct 313 ms 21368 KB Output is correct
18 Correct 166 ms 20992 KB Output is correct
19 Correct 317 ms 21292 KB Output is correct
20 Correct 285 ms 20880 KB Output is correct
21 Correct 300 ms 21188 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1088 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1084 KB Output is correct
10 Correct 1 ms 1092 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1092 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1088 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 2 ms 1224 KB Output is correct
14 Correct 3 ms 1228 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 2 ms 1228 KB Output is correct
20 Correct 3 ms 1300 KB Output is correct
21 Correct 2 ms 1264 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 3 ms 1228 KB Output is correct
24 Correct 2 ms 1236 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 1088 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1084 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 2 ms 1228 KB Output is correct
14 Correct 3 ms 1228 KB Output is correct
15 Correct 4 ms 1228 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 2 ms 1096 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 3 ms 1228 KB Output is correct
20 Correct 3 ms 1272 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1228 KB Output is correct
23 Correct 3 ms 1228 KB Output is correct
24 Correct 2 ms 1228 KB Output is correct
25 Correct 352 ms 19764 KB Output is correct
26 Correct 386 ms 19948 KB Output is correct
27 Correct 422 ms 20704 KB Output is correct
28 Correct 442 ms 21308 KB Output is correct
29 Correct 416 ms 21360 KB Output is correct
30 Correct 189 ms 11768 KB Output is correct
31 Correct 345 ms 20644 KB Output is correct
32 Correct 395 ms 21368 KB Output is correct
33 Correct 245 ms 21020 KB Output is correct
34 Correct 365 ms 21364 KB Output is correct
35 Correct 356 ms 20992 KB Output is correct
36 Correct 362 ms 21120 KB Output is correct
37 Correct 350 ms 19944 KB Output is correct