oj.uz

답안 #71642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71642 2018-08-25T09:35:24 Z istlemin 금 캐기 (IZhO14_divide) C++14
0 / 100
 301 ms 50516 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 = -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 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
0 / 17.0

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

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 576 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 5 ms 868 KB Output is correct
5 Incorrect 4 ms 876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2540 KB Output is correct
2 Correct 23 ms 4456 KB Output is correct
3 Correct 25 ms 4456 KB Output is correct
4 Correct 120 ms 20876 KB Output is correct
5 Correct 129 ms 22184 KB Output is correct
6 Correct 265 ms 44396 KB Output is correct
7 Correct 301 ms 46312 KB Output is correct
8 Correct 262 ms 48260 KB Output is correct
9 Correct 231 ms 49928 KB Output is correct
10 Incorrect 227 ms 50516 KB Output isn't correct
11 Halted 0 ms 0 KB -