Submission #234945

#	Time	Username	Problem	Language	Result	Execution time	Memory
234945		Atalasion	Art Exhibition (JOI18_art)	C++14	100 / 100	937 ms	37552 KiB

art

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000010;
const ll LOG = 25;

struct per{
	ll a, b;
};
ll seg[N << 2], lazy[N << 2], n;
per A[N];

void modify(int id, ll x){
	seg[id] += x;
	lazy[id] += x;
}

void shift(int id){
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = 0;
}


void add(int id, int lq, int rq, ll x, int l, int r){
	if (rq <= l || r <= lq)return;
	if (lq <= l && r <= rq){
		modify(id, x);
		return;
	}
	int md = (l +r) >> 1;
	shift(id);
	add(id << 1, lq, rq, x, l, md);
	add(id << 1 | 1, lq, rq, x, md, r);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

bool cmp(per x, per y){
	return x.a < y.a;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> A[i].a >> A[i].b;
	}
	sort(A + 1, A + n + 1, cmp);
	ll ans = 0;
	for (int i = 1; i <= n; i++){
		add(1, i, n + 1, A[i].b, 1, n + 1);
		add(1, i, i + 1, -A[i].a, 1, n + 1);
	}
	for (int i = 1; i <= n; i++){
		add(1, i, n + 1, A[i].a, 1, n + 1);
		ans = max(ans, seg[1]);
		add(1, i, n + 1, -A[i].b, 1, n + 1);
		add(1, i, n + 1, -A[i].a, 1, n + 1);
	}
	cout << ans;







	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50