Submission #84370

#	Time	Username	Problem	Language	Result	Execution time	Memory
84370		Alexa2001	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	525 ms	55720 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 1e5 + 5;

struct segment
{
    int x, y;
    bool operator < (const segment &other) const
    {
        return x + y < other.x + other.y;
    }
};
vector<segment> v;
map<int,int> mp;
ll dp1[Nmax], dp2[Nmax];
ll ans = 0;
int ord[2*Nmax];


struct AIB
{
    int a[2*Nmax];
    ll b[2*Nmax];

    int ub(int x) { return (x&(-x)); }

    void clear()
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
    }

    void upd(int pos, int A, int B)
    {
        for(; pos<=mp.size(); pos+=ub(pos))
            a[pos] += A, b[pos] += B;
    }

    ll query(int Pos)
    {
        int A = 0, pos = Pos; ll B = 0;
        for(; pos; pos-=ub(pos))
            A += a[pos], B += b[pos];
        return (ll) A * ord[Pos] + B;
    }

    void update(int X, int Y)
    {
        int x = mp[X], y = mp[Y];
        upd(y, 1, -Y);
        upd(1, -1, X);
        upd(x, 1, -X);
    }
} aib;


void init()
{
    sort(v.begin(), v.end());

    int cnt = 0;
    for(auto &it : mp)
    {
        it.second = ++cnt;
        ord[cnt] = it.first;
    }
}

void prefix()
{
    aib.clear();
    int i, id = 1;
    for(i=0; i<v.size(); ++i)
    {
        aib.update(v[i].x, v[i].y);
        while(id<mp.size() && aib.query(id) > aib.query(id+1)) ++id;
        dp1[i] = aib.query(id);
    }
}

void suffix()
{
    aib.clear();
    int i, id = mp.size();
    for(i=v.size()-1; i>=0; --i)
    {
        aib.update(v[i].x, v[i].y);
        while(id>1 && aib.query(id) > aib.query(id-1)) --id;
        dp2[i] = aib.query(id);
    }
}

int main()
{
 //   freopen("input", "r", stdin);

    int i, N, K, x, y;
    char tip1, tip2;

    cin >> K >> N;
    for(i=1; i<=N; ++i)
    {
        cin >> tip1 >> x >> tip2 >> y;
        if(x > y) swap(x, y);

        ans += y - x;
        if(tip1 != tip2)
        {
            ++ans;
            v.push_back({x, y});
            mp[x] = 1; mp[y] = 1;
        }
    }

    if(v.empty())
    {
        cout << ans << '\n';
        return 0;
    }

    init();
    prefix();
    suffix();

    K = min(K, (int) mp.size());
    K = min(K, (int) v.size());

    ll best;
    best = dp1[v.size()-1];

    if(K == 2)
        for(i=0; i<(int) v.size()-1; ++i) best = min(best, dp1[i] + dp2[i+1]);

    cout << 2 * best + ans << '\n';

    return 0;
}

Compilation message (stderr)

bridge.cpp: In member function 'void AIB::upd(int, int, int)':
bridge.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pos<=mp.size(); pos+=ub(pos))
               ~~~^~~~~~~~~~~
bridge.cpp: In function 'void prefix()':
bridge.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~
bridge.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(id<mp.size() && aib.query(id) > aib.query(id+1)) ++id;
               ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37