Submission #625264

#	Time	Username	Problem	Language	Result	Execution time	Memory
625264		ansol4328	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	3 ms	724 KiB

bulldozer

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

struct SegTree{
    struct node{
        ll L, R, sum, mx;
    };
    vector<node> tree;
    int base;
    SegTree(int a){
        for(base=1 ; base<a ; base<<=1);
        tree.resize(base*2);
        base--;
    }
    node add(node &lhs, node &rhs){
        node ret;
        ret.sum=lhs.sum+rhs.sum;
        ret.L=max(lhs.L,lhs.sum+rhs.L);
        ret.R=max(rhs.R,rhs.sum+lhs.R);
        ret.mx=max({lhs.R+rhs.L, lhs.mx, rhs.mx});
        return ret;
    }
    void updt(int i, ll v){
        tree[i+=base]={v,v,v,v};
        for(i>>=1 ; i ; i>>=1) tree[i]=add(tree[i*2],tree[i*2+1]);
    }
    ll qry(){ return tree[1].mx; }
};

struct frac{
    ll a, b;
    bool operator< (const frac &rhs) const{
        return a*rhs.b>rhs.a*b;
    }
    bool operator== (const frac &rhs) const{
        return a*rhs.b==rhs.a*b;
    }
};

struct line{
    frac slp;
    int p1, p2;
    bool operator< (const line &rhs) const{
        return slp<rhs.slp;
    }
};

struct uf{
    vector<int> p;
    vector<ll> w;
    uf(int a) : p(a+5,-1), w(a+5,0) {}
    int f(int a){ return p[a]==-1 ? a : p[a]=f(p[a]); }
    void u(int x, int y){
        x=f(x), y=f(y);
        if(x==y) return;
        p[x]=y; w[y]+=w[x];
    }
};

int N;
pair<P,ll> M[2005];
int id[2005], inv[2005];
//id = sorted state, inv = inverse of id
vector<line> lst;
vector<int> grp[2005];

void fastio(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
}

int main(){
    fastio();
    cin >> N;
    for(int i=1 ; i<=N ; i++){
        cin >> M[i].fi.fi >> M[i].fi.se >> M[i].se;
    }
    if(N==1){
        cout << max(0LL,M[1].se) << '\n'; return 0;
    }
    vector<frac> F;
    sort(M+1,M+1+N);
    for(int i=1 ; i<=N ; i++){
        for(int j=i+1 ; j<=N ; j++){
            lst.pb({{M[i].fi.se-M[j].fi.se, M[i].fi.fi-M[j].fi.fi},i,j});
            F.pb(lst.back().slp);
        }
    }
    sort(lst.begin(),lst.end());
    sort(F.begin(),F.end());
    F.erase(unique(F.begin(),F.end()),F.end());

    SegTree seg(N);
    uf T(N);
    for(int i=1 ; i<=N ; i++) seg.updt(i,M[i].se), id[i]=inv[i]=i, T.w[i]=M[i].se;
    int cur=0;
    ll ans=max(0LL,seg.qry());
    for(auto slp : F){
//        cout << slp.a << '/' << slp.b << ' ' ;
        set<int> S;
        for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
            //union
            T.u(lst[cur].p1,lst[cur].p2);
            S.insert(lst[cur].p1);
            S.insert(lst[cur].p2);
        }
        vector<int> tmp;
        for(int p : S){
            if(T.f(p)==p) tmp.pb(p), seg.updt(inv[p],T.w[p]);
            else seg.updt(inv[p],0);
            grp[T.f(p)].pb(inv[p]);
        }
        ans=max(ans,seg.qry());
        //re-ordering
        for(int G : tmp){
            sort(grp[G].begin(),grp[G].end());
            for(int i=0, j=(int)grp[G].size()-1 ; i<j ; i++, j--){
                int x=grp[G][i], y=grp[G][j];
                swap(inv[id[x]],inv[id[y]]);
                swap(id[x],id[y]);
            }
            grp[G].clear();
        }
        // for(int i=1 ; i<=N ; i++) cout << id[i] << ' ';
        // cout << '\n';
        //roll back
        for(int p : S){
            T.w[p]=M[p].se; T.p[p]=-1;
            seg.updt(inv[p],T.w[p]);
        }
    }
    ans=max(ans,seg.qry());
    cout << ans;
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
      |               ~~~^~~~~~~~~~~

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