Submission #147156

#	Time	Username	Problem	Language	Result	Execution time	Memory
147156		jh05013	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	846 ms	91432 KiB

bulldozer

#include <bits/stdc++.h>
#define entire(x) begin(x),end(x)
#define dbgv(V) {for(auto x:V)cout<<x<<' ';cout<<endl;}
using namespace std;
typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Segnode{
    ll sum, ans, L, R;

    Segnode(): sum{0}, ans{-INF}, L{-INF}, R{-INF} {}
    void operator=(ll x){
        sum = ans = L = R = x;
    }
    void combine(Segnode A, Segnode B){
        sum = A.sum + B.sum;
        L = max(A.L, A.sum + B.L);
        R = max(B.R, B.sum + A.R);
        ans = max({A.ans, B.ans, A.R+B.L});
    }
};

struct Segtree{    
    int n; vector<Segnode> arr;
    Segtree(int sz): n{1} {
        while(n < sz) n<<=1;
        arr.resize(n*2);
    }
    Segnode &operator[](int i){return arr[i+n];}
    void initialize(){for(int i=n-1; i>=0; i--) arr[i].combine(arr[2*i], arr[2*i+1]);}
    void update(int i){for(i+= n; i>>=1;) arr[i].combine(arr[i<<1], arr[i<<1|1]);}
    Segnode query(int l, int r){
        Segnode resl, resr, ans;
        for(l+= n, r+= n+1; l < r; l/= 2, r/= 2){
            if(l&1) resl.combine(resl, arr[l++]);
            if(r&1) resr.combine(arr[--r], resr);
        }
        ans.combine(resl, resr);
        return ans;
    }
};

struct Point{ll x, y;};
struct Frac{
    ll n, d;
    Frac(){Frac(0,0);}
    Frac(ll a, ll b){
        if(b==0) n=abs(a), d=0;
        else if(b<0) n=-a, d=-b;
        else n=a, d=b;
    }
};
bool operator==(const Frac &A, const Frac &B){
    return A.n*B.d == A.d*B.n;
}
bool operator<(const Frac &A, const Frac &B){
    return A.n*B.d < A.d*B.n;
}

vector<Point> P;
const ll fs = -2000000005;
int main(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    
    // IO and special case
    int n; cin>>n;
    P.resize(n);
    vector<ll> score(n);
    for(int i=0; i<n; i++) cin>>P[i].x>>P[i].y>>score[i];
    if (n == 1){cout<<max(0LL,score[0]); return 0;}

    // (Slope, intercept, p1, p2)
    vector<tuple<Frac, Frac, int, int>> slope;
    for(int i=0; i<n; i++) for(int j=i+1; j<n; j++){
        Frac a(P[i].y-P[j].y, P[i].x-P[j].x), b;
        if(a.d == 0) b = Frac(P[i].x, 1);
        else b = Frac(P[i].y*a.d - P[i].x*a.n, a.d);
        slope.push_back(make_tuple(a, b, i, j));
    }
    sort(entire(slope));
    slope.push_back(slope[0]); // sentinel

    // Points sorted by y-intercept
    vector<int> C(n);
    iota(entire(C), 0);
    sort(entire(C), [](const int &a, const int &b)
        {return P[a].y-P[a].x*fs < P[b].y-P[b].x*fs;});
    Segtree ST(n);
    for(int i=0; i<n; i++) ST[i] = score[C[i]];
    ST.initialize();
    ll ans = max(0LL, ST.query(0,n-1).ans);

    // Reverse map
    vector<int> rev(n), colinear;
    for(int i=0; i<n; i++) rev[C[i]] = i;

    // Scan
    size_t ss = slope.size()-1; // Excluding sentinel
    for(size_t si=0; si<ss; si++){
        Frac a1,b1; int i1,j1; tie(a1,b1,i1,j1) = slope[si];
        Frac a2,b2; int i2,j2; tie(a2,b2,i2,j2) = slope[si+1];
        colinear.push_back(rev[i1]);
        colinear.push_back(rev[j1]);
        if(si != ss-1 && a1 == a2 && b1 == b2) continue;
        // Invert
        int l = *min_element(entire(colinear));
        int r = *max_element(entire(colinear));
        while(l < r){
            int pl = C[l], pr = C[r];
            ST[l] = score[pr], ST.update(l);
            ST[r] = score[pl], ST.update(r);
            rev[pl] = r, rev[pr] = l;
            swap(C[l], C[r]);
            l++, r--;
        }
        colinear.clear();
        if(si != ss-1 && a1 == a2) continue;
        ll V = ST.query(0,n-1).ans;
        ans = max(ans, V);
    }
    cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20