Submission #263340

#	Time	Username	Problem	Language	Result	Execution time	Memory
263340		Kastanda	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	395 ms	25460 KiB

bridge

// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 100905 * 2;
int n, k, ID[N];
ll dp[N], FA[N], FB[N], FC[N];
pair < ll , ll > FL[N], FR[N];
pair < int , int > A[N];
vector < int > U, V, S[N], E[N];
inline void AddFen(int i, int a, int b, int c)
{
        for (i += 10; i < N; i += i & - i)
                FA[i] += a, FB[i] += b, FC[i] += c;
}
inline void AddFen(int l, int r, int a, int b, int c)
{
        AddFen(l, a, b, c);
        AddFen(r, -a, -b, -c);
}
inline vector < ll > GetFen(int i)
{
        vector < ll > rt = {0, 0, 0};
        for (i += 10; i; i -= i & - i)
                rt[0] += FA[i], rt[1] += FB[i], rt[2] += FC[i];
        return rt;
}
inline void Add(int i, int val)
{
        // [0, ID[i]] , -U[A[i]].y   ,  .x   , .y
        AddFen(-1, ID[i] + 1, -U[A[i].y] * val, 0, 1 * val);
        // [ID[i] + 1, N) U[A[i].x]
        AddFen(ID[i] + 1, N, U[A[i].x] * val, -1 * val, 0);
}
inline ll Query(int a, int b)
{
        ll rt = 0;
        rt += FL[a].x + FL[a].y * (ll)U[a];
        rt += FR[b].x + FR[b].y * (ll)U[b];

        int lb = (int)(lower_bound(V.begin(), V.end(), U[a] + U[b]) - V.begin());
        vector < ll > tmp = GetFen(lb);
        rt += tmp[0];
        rt += tmp[1] * (ll)U[a];
        rt += tmp[2] * (ll)U[b];

        return rt;
}
void Solve(int l, int r, int le, int ri)
{
        if (r < l)
                return ;
        int md = (l + r) >> 1, opt = -1;
        // [le, l) is added ...
        // Extending from right to [le, md]
        for (int i = l; i <= md; i ++)
                for (int j : E[i])
                        if (A[j].x >= le) // Should be added
                                Add(j, 1);
        // [le, md] is added, time for querying ..
        dp[md] = (ll)(1e18);
        for (int i = le; i <= min(ri, md); i ++)
        {
                ll val = Query(i, md);
                if (dp[md] >= val)
                        dp[md] = val, opt = i;
                // Shrinking from left to [i + 1, md]
                for (int j : S[i])
                        if (A[j].y <= md) // Should be deleted
                                Add(j, -1);
        }
        // Now we have [min(ri, md) + 1, md]
        // Extending from left to [opt, md]
        for (int i = min(ri, md); i >= opt; i --)
                for (int j : S[i])
                        if (A[j].y <= md) // Should be added
                                Add(j, 1);
        Solve(md + 1, r, opt, ri);
        // Extending from left to [le, md]
        for (int i = opt - 1; i >= le; i --)
                for (int j : S[i])
                        if (A[j].y <= md)
                                Add(j, 1);
        // Shrinking from right to [le, l)
        for (int i = md; i >= l; i --)
                for (int j : E[i])
                        if (A[j].x >= le)
                                Add(j, -1);
        Solve(l, md - 1, le, opt);
}
int main()
{
        ll SM = 0;
        cin >> k >> n;
        for (int i = 1; i <= n; i ++)
        {
                int a, b;
                //char sa[1], sb[1];
                string sa, sb;
                //scanf("%s%d%s%d", sa, &a, sb, &b);
                cin >> sa >> a >> sb >> b;
                if (a > b) swap(a, b);
                SM += b - a;
                if (sa[0] == sb[0])
                        {n --; i --; continue;}
                SM ++;
                A[i] = {a, b};
                U.push_back(a);
                U.push_back(b);
                V.push_back(a + b);
        }
        if (!n)
                return !printf("%lld\n", SM);
        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        sort(V.begin(), V.end());
        V.resize(unique(V.begin(), V.end()) - V.begin());
        for (int i = 1; i <= n; i ++)
        {
                ID[i] = (int)(lower_bound(V.begin(), V.end(), A[i].x + A[i].y) - V.begin());
                A[i].x = (int)(lower_bound(U.begin(), U.end(), A[i].x) - U.begin());
                A[i].y = (int)(lower_bound(U.begin(), U.end(), A[i].y) - U.begin());
                S[A[i].x].push_back(i);
                E[A[i].y].push_back(i);
        }
        for (int i = 0; i < (int)U.size(); i ++)
        {
                // Sum of .y for all .y <= U[i]
                if (i)
                        FL[i] = FL[i - 1];
                for (int j : E[i])
                        FL[i].x -= U[i], FL[i].y ++;
        }
        for (int i = (int)U.size() - 1; ~ i; i --)
        {
                // Sum of .x for all .x >= U[i]
                FR[i] = FR[i + 1];
                for (int j : S[i])
                        FR[i].x += U[i], FR[i].y --;
        }
        ll Mn = (ll)(1e18);
        for (int i = 0; i < (int)U.size(); i ++)
        {
                ll rt = 0;
                rt += FL[i].x + FL[i].y * (ll)U[i];
                rt += FR[i].x + FR[i].y * (ll)U[i];
                Mn = min(Mn, rt);
        }
        if (k == 1)
                return !printf("%lld\n", Mn * 2LL + SM);
        //Solve(0, (int)U.size() - 1, 0, (int)U.size() - 1);
        int opt = 0;
        for (int i = 0; i <= (int)U.size(); i ++)
        {
                for (int j : E[i])
                        if (A[j].x >= opt)
                                Add(j, 1);
                dp[i] = Query(opt, i);
                while (opt < i)
                {
                        for (int j : S[opt])
                                if (A[j].y <= i)
                                        Add(j, -1);
                        ll val = Query(opt + 1, i);
                        if (val <= dp[i])
                                dp[i] = val, opt ++;
                        else
                        {
                                for (int j : S[opt])
                                        if (A[j].y <= i)
                                                Add(j, 1);
                                break;
                        }
                }
        }
        for (int i = 0; i < (int)U.size(); i ++)
                Mn = min(Mn, dp[i]);
        return !printf("%lld\n", Mn * 2LL + SM);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:133:26: warning: unused variable 'j' [-Wunused-variable]
  133 |                 for (int j : E[i])
      |                          ^
bridge.cpp:140:26: warning: unused variable 'j' [-Wunused-variable]
  140 |                 for (int j : S[i])
      |                          ^

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