oj.uz

답안 #258435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258435 2020-08-05T23:09:00 Z SpeedOfMagic Art Exhibition (JOI18_art) C++17
0 / 100
 0 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segTree {
    const int nothing = -1e9;
    vector<int> val, lazy;
    int n;

    int f(int a, int b) { return max(a, b); }

	inline void pushdown(int cur) {
	    if (lazy[cur])
            val[cur] += lazy[cur];
		if (cur < n && lazy[cur]) {
			lazy[cur << 1] += lazy[cur];
			lazy[cur << 1 | 1] += lazy[cur];
		}
		lazy[cur] = 0;
	}

    void update(int l, int r, int value, int cur = 1, int ll = 1, int rr = 1e9) {
        rr = min(rr, n);
		pushdown(cur);
        if (l > r)
            return;
        if (l == ll && r == rr) {
			lazy[cur] = value;
			pushdown(cur);
			return;
		}

        int mid = (ll + rr) >> 1;
		update(l, min(r, mid), value, cur << 1, ll, mid);
		update(max(l, mid + 1), r, value, cur << 1 | 1, mid + 1, rr);
        val[cur] = f(val[cur << 1], val[cur << 1 | 1]);
    }

    int query(int l, int r, int cur = 1, int ll = 1, int rr = 1e9) {
        rr = min(rr, n);
		pushdown(cur);
        if (l > r)
            return nothing;
        if (l == ll && r == rr)
            return val[cur];

        int mid = (ll + rr) >> 1;
        return f(query(l, min(r, mid), cur << 1, ll, mid), query(max(l, mid + 1), r, cur << 1 | 1, mid + 1, rr));
    }

    segTree(vector<int> arr) {
        for (n = arr.size(); n & (n - 1); n++) {}
        val = vector<int>(n * 2, nothing);
		lazy = vector<int>(n * 2, 0);
        for (int i = n + arr.size() - 1; i; i--)
            val[i] = ((i < n) ? f(val[i << 1], val[i << 1 | 1]) : arr[i - n]);
    }
};

signed main() {
	int n; cin >> n;
	pair<int, int> p[n];
	for (int i = 0; i < n; ++i) {
		cin >> p[i].first >> p[i].second;
	}
	sort(p, p + n);
	vector<int> d(n);
	int s = 0;
	for (int i = 0; i < n; ++i) {
		s += p[i].second;
		d[i] = s - p[i].first;
	}
	segTree st(d);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = max(ans, st.query(i + 1, n) + p[i].first);
		st.update(i + 1, n, -p[i].second);
	}
	cout << ans << endl;
	
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -