oj.uz

Submission #71633

# Submission time Handle Problem Language Result Execution time Memory
71633 2018-08-25T09:22:32 Z istlemin Divide and conquer (IZhO14_divide) C++14
48 / 100
 576 ms 263168 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;

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 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 pos,ll val){
        ll diff = val-query(pos,pos+1);
        if(diff>0)
			add(pos,pos+1,diff);
    }


    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];
    }

    Node st(-1e9,1e9);
    ll currentZero = 0;

    ll 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:31:19: warning: 'st.Node::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
             right = new Node((dn+up)/2,up);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:113:10: note: 'st.Node::right' was declared here
     Node st(-1e9,1e9);
          ^~
divide.cpp:31:19: warning: 'st.Node::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
             right = new Node((dn+up)/2,up);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:113:10: note: 'st.Node::left' was declared here
     Node st(-1e9,1e9);
          ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 3 ms 772 KB Output is correct
6 Correct 3 ms 1032 KB Output is correct
7 Correct 2 ms 1032 KB Output is correct
8 Correct 4 ms 1032 KB Output is correct
9 Correct 2 ms 1032 KB Output is correct
10 Correct 6 ms 1032 KB Output is correct
11 Correct 3 ms 1032 KB Output is correct
12 Correct 3 ms 1076 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1076 KB Output is correct
2 Correct 3 ms 1076 KB Output is correct
3 Correct 6 ms 3076 KB Output is correct
4 Correct 7 ms 3856 KB Output is correct
5 Correct 8 ms 4784 KB Output is correct
6 Correct 3 ms 4784 KB Output is correct
7 Correct 8 ms 4784 KB Output is correct
8 Correct 9 ms 4784 KB Output is correct
9 Correct 7 ms 4784 KB Output is correct
10 Correct 10 ms 4784 KB Output is correct
11 Correct 30 ms 13832 KB Output is correct
12 Correct 31 ms 17788 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17788 KB Output is correct
2 Correct 36 ms 17788 KB Output is correct
3 Correct 23 ms 17788 KB Output is correct
4 Correct 36 ms 17788 KB Output is correct
5 Correct 37 ms 17788 KB Output is correct
6 Correct 47 ms 17788 KB Output is correct
7 Correct 45 ms 17788 KB Output is correct
8 Correct 77 ms 19444 KB Output is correct
9 Correct 394 ms 188968 KB Output is correct
10 Correct 244 ms 188968 KB Output is correct
11 Correct 420 ms 217984 KB Output is correct
12 Runtime error 576 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.