Submission #949867

#	Time	Username	Problem	Language	Result	Execution time	Memory
949867		dimashhh	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1257 ms	107164 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5+ 5, MOD = 998244353;
#define int ll
int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
struct node{
    ll res,mxl,mxr,sum;
};
node T[N * 4];
node merge(node l,node r){
    node ret;
    ret.sum = l.sum + r.sum;
    ret.res = max({l.res,r.res});
    ret.res = max(ret.res,l.mxr + r.mxl);
    ret.mxr = max(r.mxr,r.sum + l.mxr);
    ret.mxl = max(l.mxl,l.sum + r.mxl);
    return ret;
}
void upd(int pos,ll val,int v = 1,int tl = 1,int tr = n){
    if(tl == tr){
        T[v].sum = val;
        T[v].res = T[v].mxr = T[v].mxl = max(0ll,val);
    }else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,v+v,tl,tm);
        else upd(pos,val,v+v+1,tm+1,tr);
        T[v] = merge(T[v+v],T[v+v+1]);
    }
}
void out(int v = 1,int tl = 1,int tr = n){
    if(tl == tr){
        cout << tl << ' ' << T[v].sum << '\n';
    }else{
        int tm = (tl + tr) >> 1;
        out(v+v,tl,tm);
        out(v+v+1,tm+1,tr);
    }
}
void test() {
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i] >> w[i];
    }
    if(n == 1){
        cout << max(0ll,w[1]) << '\n';
        return;
    }
    vector<pair<long double,pair<int,int>>> cur;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            long double val;
            if(x[i] == x[j]) val = 2e9;
            else val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
            cur.push_back({val,{i,j}});
        }
    }
    ll res = 0;
    sort(cur.rbegin(),cur.rend());
    int ii = cur[0].second.first,jj = cur[0].second.second;
    for(int i = n;i >= 1;i--){
        if(x[ii] == x[jj]){
            a.push_back({x[i],y[i],i});
        }else{
            a.push_back({x[i],-y[i],i});
        }
    }
    sort(a.begin(),a.end());
    for(int i = 0;i < (int)a.size();i++){
        pos[a[i][2]] = i + 1;
        t[i + 1] = a[i][2];
        upd(i+1,w[a[i][2]]);
    }
    for(int i = 0;i < (int)cur.size();i++){
//        for(int j = 1;j <= n;j++){
//            cout << t[j] << ' ';
//        }
//        cout << '\n';
        vector<pair<int,int>> ss,s1;
        for(int j = i;j <= (int)cur.size();j++){
            if(j == (int)cur.size() || cur[j].first != cur[i].first){
                i = j - 1;
                break;
            }
            int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
                                                                                      pos[cur[j].second.second]);
            ss.push_back({L,R});
        }
        vector<ll> sums;
        sort(ss.begin(),ss.end());
        ll mn = 0,curs = 0;
        ll max_checked;
        for(int j = 0;j < (int)ss.size();j++) {
            if (j && max_checked >= ss[j].second) continue;
            int mx = ss[j].second;
            for (int k = j; k <= (int) ss.size(); k++) {
                if (k == (int) ss.size() || ss[k].first != ss[j].first) {
                    j = k - 1;
                    break;
                }
                max_checked = ss[k].second;
                mx = ss[k].second;
            }
            int l = ss[j].first, r = mx;
            s1.push_back({l, r});
//            cout << l << ' ' << r << '\n';
            while (l < r) {
                swap(t[l], t[r]);
                upd(l, w[t[l]]);
                upd(r, w[t[r]]);
                pos[t[l]] = l;
                pos[t[r]] = r;
                l++;
                r--;
            }
        }
//        cout << T[1].res << "x\n";
//        cout << '\n';
//        for(int j = 1;j <= n;j++){
//            cout << j << ' ' << w[t[j]] << '\n';
//        }
//        cout << '\n';
        for(auto [L,R]:s1){
            ll f = w[t[L]];
//            cout << L << ' ' << R << "x\n";
            for(int j = L + 1;j <= R;j++){
//                upd(j,0);
                f += w[t[j]];
            }
//            upd(L,f);
        }
//        cout << '\n';
//        out();
//        cout << T[1].res << '\n';
        res = max(res,T[1].res);
        for(auto [L,R]:s1){
            for(int j = L;j <= R;j++){
//                upd(j,w[t[j]]);
            }
        }
    }
    cout << res << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Compilation message (stderr)

bulldozer.cpp: In function 'void test()':
bulldozer.cpp:96:12: warning: unused variable 'mn' [-Wunused-variable]
   96 |         ll mn = 0,curs = 0;
      |            ^~
bulldozer.cpp:96:19: warning: unused variable 'curs' [-Wunused-variable]
   96 |         ll mn = 0,curs = 0;
      |                   ^~~~

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