oj.uz

답안 #71636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71636 2018-08-25T09:26:28 Z istlemin 금 캐기 (IZhO14_divide) C++14
0 / 100
 34 ms 14996 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 int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

class Node {
public:
    ll data = -1e9;
	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 member function 'll Node::query(ll, ll)':
divide.cpp:61:34: warning: overflow in implicit constant conversion [-Woverflow]
         if(a>=up||b<=dn) return -1e18;
                                  ^~~~
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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Incorrect 4 ms 1012 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 3 ms 1012 KB Output is correct
3 Correct 5 ms 2500 KB Output is correct
4 Correct 7 ms 3064 KB Output is correct
5 Incorrect 8 ms 3736 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6196 KB Output is correct
2 Correct 29 ms 12676 KB Output is correct
3 Incorrect 34 ms 14996 KB Output isn't correct
4 Halted 0 ms 0 KB -