oj.uz

Submission #71643

# Submission time Handle Problem Language Result Execution time Memory
71643 2018-08-25T09:36:27 Z istlemin Divide and conquer (IZhO14_divide) C++14
100 / 100
 325 ms 44112 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 3 ms 636 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 3 ms 804 KB Output is correct
10 Correct 4 ms 804 KB Output is correct
11 Correct 3 ms 804 KB Output is correct
12 Correct 4 ms 804 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 804 KB Output is correct
2 Correct 3 ms 804 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 6 ms 1144 KB Output is correct
8 Correct 7 ms 1180 KB Output is correct
9 Correct 7 ms 1344 KB Output is correct
10 Correct 9 ms 1644 KB Output is correct
11 Correct 16 ms 2960 KB Output is correct
12 Correct 17 ms 3072 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3072 KB Output is correct
2 Correct 31 ms 4984 KB Output is correct
3 Correct 29 ms 4984 KB Output is correct
4 Correct 139 ms 20252 KB Output is correct
5 Correct 135 ms 20336 KB Output is correct
6 Correct 325 ms 39528 KB Output is correct
7 Correct 297 ms 39536 KB Output is correct
8 Correct 322 ms 39536 KB Output is correct
9 Correct 268 ms 39536 KB Output is correct
10 Correct 268 ms 39536 KB Output is correct
11 Correct 324 ms 41740 KB Output is correct
12 Correct 287 ms 44112 KB Output is correct