Submission #455292

#	Time	Username	Problem	Language	Result	Execution time	Memory
455292		nonsensenonsense1	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	1633 ms	37728 KiB

bridge

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#ifdef KAZAR
    #define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
    #define eprintf(...) 0
#endif

using namespace std;

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}

typedef long long ll;
typedef pair<int, int> ii;

const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;

inline int read(){int x;scanf(" %d",&x);return x;}

const int N = 3e5 + 100;

int n;
char p1[N], p2[N];
int x1[N], x2[N];
vector<int> xs;

inline int getid(int x){
    return lower_bound(all(xs), x) - xs.begin();
}

int cnt_start[N], cnt_end[N];
ll lf[N], rg[N];

void pre(){
    for(int i = 1; i <= n; i++){
        if(p1[i] == p2[i])
            continue;
        cnt_start[getid(x1[i])]++;
        cnt_end[getid(x2[i])]++;
    }
    int sz = xs.size();
    {
        ll sumx = 0;
        int cnt = 0;
        for(int i = 0; i < sz; i++){
            lf[i] += (ll)xs[i] * cnt - sumx;
            sumx += (ll)xs[i] * cnt_end[i];
            cnt += cnt_end[i];
        }
    }{
        ll sumx = 0;
        int cnt = 0;
        for(int i = sz - 1; i >= 0; i--){
            rg[i] += sumx - (ll)xs[i] * cnt;
            sumx += (ll)xs[i] * cnt_start[i];
            cnt += cnt_start[i];
        }
    }
}

ll solve_one(){
    ll res = longinf;
    for(int i = 0; i < xs.size(); i++){
        umin(res, lf[i] + rg[i]);
    }
    return res;
}

class fenwick{
public:
    ll f[N];
    void add(int x,ll v){
        ++x;
        while(x < N){
            f[x] += v;
            x += x & -x;
        }
    }
    ll get(int l,int r){
        if(l > r)
            return 0;
        ++l; ++r;
        ll res = 0;
        for(int i = r; i > 0; i -= i & -i)
            res += f[i];
        for(int i = l - 1; i > 0; i -= i & -i)
            res -= f[i];
        return res;
    }
};

int L, R;
fenwick sumx1, sumx2, cnt;

void add(int x1,int x2,int c){
    int id = getid(x1 + x2);
    sumx1.add(id, x1 * c);
    sumx2.add(id, x2 * c);
    cnt.add(id, c);
}

int used[N];
vector<ii> vends[N];
vector<ii> vbegs[N];

void addL(int l,int r,int c){
    for(int i = 0; i < vends[l].size(); i++){
        int v = vends[l][i].first;
        if(v > xs[r]) break;
        used[vends[l][i].second] = c;
        add(xs[l], v, c);
    }
}

void addR(int l,int r,int c){
    for(int i = 0; i < vbegs[r].size(); i++){
        int v = vbegs[r][i].first;
        if(v < xs[l]) break;
        used[vbegs[r][i].second] = c;
        add(v, xs[r], c);
    }
}

ll ans = longinf;

void init(){
    L = 0, R = 0;
    addL(0, 0, +1);
}

void fix(int l,int r){
    while(R < r) addR(L, ++R, +1);
    while(R > r) addR(L, R--, -1);
    while(L > l) addL(--L, R, +1);
    while(L < l) addL(L++, R, -1);
}

int cL = 0, cR = 0;

ll calc(int l,int r){
    int sz = xs.size();
    ll res = lf[l] + rg[r];
    int id = lower_bound(all(xs), xs[l] + xs[r]) - xs.begin() - 1;
    ll cntL = cnt.get(0, id);
    ll sumxL = sumx1.get(0, id);
    res += sumxL - (ll)xs[l] * cntL;
    ll cntR = cnt.get(id + 1, sz - 1);
    ll sumxR = sumx2.get(id + 1, sz - 1);
    res += (ll)xs[r] * cntR - sumxR;
    return res;
}

void solve(int l,int r,int from,int to){
    if(l > r)
        return;
    int m = (l + r) >> 1;
    int st = max(m, from);
    ll best = longinf;
    int opt = 0;
    for(int i = st; i <= to; i++){
        fix(m, i);
        assert(L == m);
        assert(R == i);
        cL = cR = 0;
        ll t = calc(m, i);
        if(t < best){
            best = t;
            opt = i;
        }
    }
    if(best < ans){
        ans = best;
    }
    solve(m + 1, r, opt, to);
    solve(l, m - 1, from, opt);
}

ll solve_two(){
    for(int i = 1; i <= n; i++){
        if(p1[i] == p2[i])
            continue;
        vbegs[getid(x2[i])].push_back(ii(x1[i], i));
        vends[getid(x1[i])].push_back(ii(x2[i], i));
    }
    int sz = xs.size();
    for(int i = 0; i < sz; i++){
        sort(all(vbegs[i]));
        reverse(all(vbegs[i]));
        sort(all(vends[i]));
    }
    memset(used, -1, sizeof used);
    init();
    solve(0, sz - 1, 0, sz - 1);
    return ans;
}

int main(){

#ifdef KAZAR
    freopen("f.input","r",stdin);
    freopen("f.output","w",stdout);
    freopen("error","w",stderr);
#endif

    int k = read();
    n = read();

    ll more = 0;
    for(int i = 1; i <= n; i++){
        scanf(" %c %d %c %d", p1 + i, x1 + i, p2 + i, x2 + i);
        if(x1[i] > x2[i])
            swap(x1[i], x2[i]);
        xs.push_back(x1[i]);
        xs.push_back(x2[i]);
        xs.push_back(x1[i] + x2[i]);
        more += x2[i] - x1[i];
        if(p1[i] != p2[i])
            ++more;
    }

    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());

    pre();

    if(k == 1){
        printf("%lld\n", solve_one() * 2 + more);
        return 0;
    }

    printf("%lld\n", solve_two() * 2 + more);

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'll solve_one()':
bridge.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < xs.size(); i++){
      |                    ~~^~~~~~~~~~~
bridge.cpp: In function 'void addL(int, int, int)':
bridge.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i = 0; i < vends[l].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
bridge.cpp: In function 'void addR(int, int, int)':
bridge.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0; i < vbegs[r].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf(" %c %d %c %d", p1 + i, x1 + i, p2 + i, x2 + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int read()':
bridge.cpp:25:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | inline int read(){int x;scanf(" %d",&x);return x;}
      |                         ~~~~~^~~~~~~~~~

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