Submission #889546

#	Time	Username	Problem	Language	Result	Execution time	Memory
889546		dwuy	Divide and conquer (IZhO14_divide)	C++14	100 / 100	48 ms	11216 KiB

divide

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct SMT{
    int n;
    vector<int> tree;

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|1, OO);
    }

    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo+hi)>>1;
            if(pos<=mid) hi = mid, id = id<<1;
            else id = id<<1|1, lo = mid + 1;
        }
        tree[id] = min(tree[id], val);
        for(id>>=1; id; id>>=1) tree[id] = min(tree[id<<1], tree[id<<1|1]);
    }

    int get(int l, int r, int id, const int &u, const int &v){
        if(l>v || r<u) return OO;
        if(l>=u && r<=v) return tree[id];
        int mid = (l+r)>>1;
        return min(get(l, mid, id<<1, u, v), get(mid+1, r, id<<1|1, u, v));
    }

    int get(int l, int r){
        if(l>r) return OO;
        return get(1, n, 1, l, r);
    }
};

const int MX = 100005;
int n;
int p[MX];
int g[MX];
int e[MX];
int pfg[MX];
int pfe[MX];

void nhap(){
    cin >> n;
    for(int i=1 ; i<=n; i++){
        cin >> p[i] >> g[i] >> e[i];
        pfg[i] = pfg[i-1] + g[i];
        pfe[i] = pfe[i-1] + e[i];
    }
}

void solve(){
    vector<int> rv;
    for(int i=1; i<=n; i++) rv.push_back(p[i] - pfe[i-1]);
    sort(rv.begin(), rv.end());
    rv.erase(unique(rv.begin(), rv.end()), rv.end());
    SMT smt(rv.size());
    int ans = 0;
    for(int i=1; i<=n; i++){
        int pos = lower_bound(rv.begin(), rv.end(), p[i] - pfe[i-1]) - rv.begin() + 1;
        smt.update(pos, pfg[i-1]);
        pos = lower_bound(rv.begin(), rv.end(), p[i] - pfe[i]) - rv.begin() + 1;
        ans = max(ans, pfg[i] - smt.get(pos, rv.size()));
    }
    cout << ans;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52