Submission #171379

#	Time	Username	Problem	Language	Result	Execution time	Memory
171379		Swan	Divide and conquer (IZhO14_divide)	C++14	100 / 100	252 ms	23652 KiB

divide

#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
#define int long long
using namespace std;

const int maxn = 2e5+228;

struct st{
    int x;
    int d;
    int g;
    st(int xx,int gg,int dd){
        x = xx;
        d = dd;
        g = gg;
    }
    bool operator<(st b)const{
        return x < b.x;
    }
};

vector<st> v;
int tree[5*maxn];

void build(int v,int l,int r){
    if(l == r){
        tree[v] = 1e16;
        return;
    }
    int m = (l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    tree[v] = 1e16;
}

void upd(int v,int l,int r,int need,int x){
    if(l == r){
        tree[v] = min(x,tree[v]);
        return;
    }
    int m = (l+r)/2;
    if(need<=m)upd(v*2,l,m,need,x);
    else upd(v*2+1,m+1,r,need,x);
    tree[v] = min(tree[v*2],tree[v*2+1]);
}

int get_min(int v,int l,int r,int le,int re){
    if(l>=le && r <= re){
        return tree[v];
    }
    if(l > re || r < le)return 1e16;
    int m = (l+r)/2;
    int a = get_min(v*2,l,m,le,re);
    int b = get_min(v*2+1,m+1,r,le,re);
    return min(a,b);
}

int pref1[maxn],pref2[maxn],gold[maxn];
unordered_map<int,int> irl;
unordered_map<int,int> cmp;
vector<int> w;

main(){
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    for(int i(0); i < n;i++){
        int x,g,d; cin >> x >> g >> d;
        v.push_back({x,g,d});
    }
    sort(v.begin(),v.end());
    pref1[0] = v[0].d;
    set<int> s;
    s.insert(v[0].x-pref2[0]);
    gold[0] = v[0].g;
    for(int i(1);i < n;i++){
        pref2[i] = pref1[i-1];
        pref1[i] = pref1[i-1]+v[i].d;
        gold[i] = gold[i-1]+v[i].g;
        s.insert(v[i].x-pref2[i]);
    }
    int pnt = 0;
    for(auto&a : s){
        w.push_back(a);
        cmp[a] = pnt;
        irl[pnt] = a;
        pnt++;
    }
    build(1,0,pnt-1);
    int ans = 0;
    for(int i(0); i < v.size();i++){
        //cout << v[i].x << endl;
        ans = max(ans,v[i].g);
        int now = v[i].x-pref1[i];
        int best = lower_bound(w.begin(),w.end(),now)-w.begin();
        int to;
        if(best != w.size()){
            to = get_min(1,0,pnt-1,best,w.size()-1);
        }else to = 1e17;
        //cout << to << ' ' << gold[i] << endl;
        upd(1,0,pnt-1,cmp[v[i].x-pref2[i]],gold[i]-v[i].g);
        ans = max(ans,gold[i]-to);
    }
    cout << ans;
}
/*
*/

Compilation message (stderr)

divide.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
divide.cpp: In function 'int main()':
divide.cpp:93:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
divide.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(best != w.size()){
            ~~~~~^~~~~~~~~~~

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