Submission #71643

#	Time	Username	Problem	Language	Result	Execution time	Memory
71643		istlemin	Divide and conquer (IZhO14_divide)	C++14	100 / 100	325 ms	44112 KiB

divide

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

vi allPos;

class Node {
public:
    ll data = -1e18;
	ll lazy = 0;
    ll dn,up;
    Node *left;
    Node *right;
	bool hasChildren = false;

    Node(ll dn,ll up):dn(dn),up(up){

    }

    void ensure(){
		if(dn+1==up) return;
        if(!hasChildren){
            left = new Node(dn,(dn+up)/2);
            right = new Node((dn+up)/2,up);
            hasChildren = true;
        }
        left->data+=lazy;
        left->lazy+=lazy;
        right->data+=lazy;
        right->lazy+=lazy;
        lazy = 0;
    }

    ll trans(ll ind){
        return lower_bound(all(allPos),ind)-allPos.begin();
    }

    void _add(ll a,ll b,ll val){
		add(trans(a),trans(b),val);
    }

    ll add(ll a,ll b,ll val){
        if(a>=up||b<=dn) return data;
        if(a<=dn&&up<=b){
            data += val;
            lazy += val;
			return data;
        } else {
			ensure();
			return data = max(left->add(a,b,val),right->add(a,b,val));
		}
    }

    void _update(ll a,ll val){
		update(trans(a),val);
    }

    void update(ll pos,ll val){
        ll diff = val-query(pos,pos+1);
        if(diff>0)
			add(pos,pos+1,diff);
    }


    ll _query(ll a,ll b){
		return query(trans(a),trans(b));
    }

    ll query(ll a,ll b){
        if(a>=up||b<=dn) return -1e18;
        if(a<=dn&&up<=b) return data;
		ensure();
		return max(left->query(a,b),right->query(a,b));
    }
};

int main(){
	cin.sync_with_stdio(false);
	/*srand(5);
    ll n = 200;
    Node st(0,n);
    vi v(n,-1e18);

    rep(i,0,300){
        ll q = rand()%3;
		ll b = rand()%n+1;
		ll a = rand()%b;
		ll val = rand()%100;
		//cout<<q<<" "<<a<<" "<<b<<" "<<val<<endl;
        if(q==0){
            rep(i,a,b) v[i] += val;
            st.add(a,b,val);
        } else if(q==1){
            ll mx = -1e18;
            rep(i,a,b) mx = max(mx,v[i]);
            if(mx!=st.query(a,b)){
                rep(i,0,n) cout<<v[i]<<" ";
                cout<<endl;
                cout<<mx<<endl;
                rep(i,0,n) cout<<st.query(i,i+1)<<" ";
                cout<<endl;
                cout<<st.query(a,b)<<endl;


				assert(false);
            }
        } else {
            v[b-1] = max(v[b-1],val);
            st.update(b-1,val);
        }
    }
    cout<<endl;*/

    ll n; cin>>n;
    vi x(n);
	vi g(n);
	vi d(n);
    rep(i,0,n){
		cin>>x[i]>>g[i]>>d[i];
    }


    ll currentZero = 0;

    ll lastX = x[0];

    set<ll> allPosSet;
	allPosSet.insert(-1e9);
	allPosSet.insert(1e9);
	rep(i,0,n){
        ll dx = x[i]-lastX;
        lastX = x[i];
        currentZero -= ( d[i]-dx);
        allPosSet.insert(currentZero+d[i]);
        allPosSet.insert(currentZero);
	}

    trav(pos,allPosSet) allPos.push_back(pos);

    Node st(0,allPos.size());
    currentZero = 0;

    lastX = x[0];

    ll best = 0;
	rep(i,0,n){
        ll dx = x[i]-lastX;
        lastX = x[i];

        ll energy = d[i]-dx;
        st._add(-1e9,1e9,g[i]);
        currentZero -= energy;
        st._update(currentZero+d[i],g[i]);

        best = max(best,st._query(currentZero,1e9));
	}

    cout<<best<<endl;

	_Exit(0);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:82:14: warning: 'st.Node::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return max(left->query(a,b),right->query(a,b));
              ^~~~
divide.cpp:149:10: note: 'st.Node::right' was declared here
     Node st(0,allPos.size());
          ^~
divide.cpp:82:14: warning: 'st.Node::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return max(left->query(a,b),right->query(a,b));
              ^~~~
divide.cpp:149:10: note: 'st.Node::left' was declared here
     Node st(0,allPos.size());
          ^~

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