oj.uz

Submission #56878

# Submission time Handle Problem Language Result Execution time Memory
56878 2018-07-13T03:13:15 Z Benq Palembang Bridges (APIO15_bridge) C++14
22 / 100
 637 ms 17088 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200005;

template<class T, int SZ> struct BIT {
    T bit[SZ+1];
    
    BIT() { memset(bit,0,sizeof bit); }
    
    void upd(int k, T val) { // add val to index k
        for( ;k <= SZ; k += (k&-k)) bit[k] += val;
    }
    
    T query(int k) {
        T temp = 0;
        for (;k > 0;k -= (k&-k)) temp += bit[k];
        return temp;
    }
    T query(int l, int r) { return query(r)-query(l-1); } // range query [l,r]
};

BIT<ll,MX> s[2];

int K,N;
ll ans = 0, mn = INF;
vpi v;
map<int,int> m;
vi rm;
pl cur;

pl operator+(const pl& l, const pl& r) { return {l.f+r.f,l.s+r.s}; }
pl operator-(const pl& l, const pl& r) { return {l.f-r.f,l.s-r.s}; }

ll eval(int x) {
    return s[1].query(x)*rm[x]+s[0].query(x);
}

ll ternary() {
    int lo = 1, hi = sz(m);
    while (lo+2<hi) {
        int l1 = (2*lo+hi)/3, r1 = (lo+2*hi)/3;
        if (eval(l1) < eval(r1)) hi = r1;
        else lo = l1;
    }
    ll z = INF;
    FOR(i,lo,hi+1) z = min(z,eval(i));
    return z;
}
void ad(int ind, int l, int r, int x) {
    s[ind].upd(l,x);
    s[ind].upd(r+1,-x);
}

void ins(int a, int b) {
    ad(1,1,m[a],-1);
    ad(0,1,m[a],a);
    ad(1,m[b],sz(m),1);
    ad(0,m[b],sz(m),-b);
}

ll pre(int x) {
    return cur.s*rm[x]-cur.f;
}

void getmn() {
    vpi ev;
    for (auto x: v) {
        ev.pb({x.f,x.s});
        ev.pb({x.s,-1});
        cur = cur+mp(x.s,1);
    }
    
    int co = 0;
    
    rm.resize(sz(m)+1);
    rm.pb(-1);
    vi tri;
    for (auto& a: m) {
        a.s = ++co;
        // cout << "HA " << a.f << " " << a.s << "\n";
        rm[co] = a.f;
    }
    
    sort(all(ev)); reverse(all(ev)); 
    int ind = 0;
    FORd(i,1,sz(m)+1) {
        while (ind < sz(ev) && ev[ind].f >= rm[i]) {
            if (ev[ind].s != -1) {
                ins(ev[ind].f,ev[ind].s);
            } else {
                cur = cur-mp(ev[ind].f,1);
            }
            ind ++;
        }
        // cout << "OH " << i << " " << rm[i] << " " << pre(i) << " " << eval(i) << "\n";
        if (K == 2)  mn = min(mn,pre(i)+ternary());
        else mn = min(mn,pre(i)+eval(i));
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> K >> N;
    m[0] = 0;
    F0R(i,N) {
        char a1, b1; int a2, b2; 
        cin >> a1 >> a2 >> b1 >> b2;
        ans += abs(a2-b2);
        if (a1 != b1) {
            v.pb({min(a2,b2),max(a2,b2)});
            ans ++;
            m[a2] = m[b2] = 0;
        }
    }
    getmn();
    cout << ans+2*mn;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 5 ms 3484 KB Output is correct
3 Correct 8 ms 3644 KB Output is correct
4 Correct 10 ms 3824 KB Output is correct
5 Correct 8 ms 3824 KB Output is correct
6 Correct 7 ms 3824 KB Output is correct
7 Correct 7 ms 3824 KB Output is correct
8 Correct 7 ms 3824 KB Output is correct
9 Correct 9 ms 3824 KB Output is correct
10 Correct 6 ms 3824 KB Output is correct
11 Correct 7 ms 3824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3824 KB Output is correct
2 Correct 6 ms 3824 KB Output is correct
3 Correct 7 ms 3824 KB Output is correct
4 Correct 9 ms 3824 KB Output is correct
5 Correct 7 ms 3824 KB Output is correct
6 Correct 7 ms 3824 KB Output is correct
7 Correct 7 ms 3824 KB Output is correct
8 Correct 8 ms 3824 KB Output is correct
9 Correct 8 ms 3824 KB Output is correct
10 Correct 7 ms 3824 KB Output is correct
11 Correct 8 ms 3824 KB Output is correct
12 Correct 94 ms 6728 KB Output is correct
13 Correct 637 ms 17088 KB Output is correct
14 Correct 188 ms 17088 KB Output is correct
15 Correct 343 ms 17088 KB Output is correct
16 Correct 94 ms 17088 KB Output is correct
17 Correct 257 ms 17088 KB Output is correct
18 Correct 319 ms 17088 KB Output is correct
19 Correct 414 ms 17088 KB Output is correct
20 Correct 139 ms 17088 KB Output is correct
21 Correct 249 ms 17088 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17088 KB Output is correct
2 Correct 5 ms 17088 KB Output is correct
3 Incorrect 5 ms 17088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17088 KB Output is correct
2 Correct 5 ms 17088 KB Output is correct
3 Incorrect 6 ms 17088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17088 KB Output is correct
2 Correct 5 ms 17088 KB Output is correct
3 Incorrect 6 ms 17088 KB Output isn't correct
4 Halted 0 ms 0 KB -