Submission #847599

#	Time	Username	Problem	Language	Result	Execution time	Memory
847599		Amaarsaa	Art Exhibition (JOI18_art)	C++14	100 / 100	293 ms	68256 KiB

art

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll mid;
struct Node{
	ll Max = 0, Has = 0;
	Node *l, *r; 
};
void Change(Node *P, ll lo, ll hi, ll st, ll fn, ll x) {
	if (st > hi || lo > fn) return ;
	if ( st <= lo && hi <= fn) {
		P -> Max += x;
		P -> Has = 1;
		return ;
	}
	if (!P -> l) P -> l = new Node();
	if (!P -> r) P -> r = new Node();
	mid = (lo + hi)/2;
	if ( P -> Has == 1) {
		P -> l -> Has = 1;
		P -> r -> Has = 1;
		P -> Has = 0;
		P -> l -> Max = P -> Max;
		P -> r -> Max = P -> Max;
	}
	Change(P -> l, lo, mid, st, fn, x);
	Change(P -> r, mid + 1, hi, st, fn, x);
	P -> Max = max ( P -> l -> Max, P -> r -> Max);
}
ll Find(Node *P, ll lo, ll hi, ll st, ll fn) {
	if (st > hi || lo > fn) return 0;
	if ( st <= lo && hi <= fn) {
		return P -> Max;
	}
	if (!P -> l) P -> l = new Node();
	if (!P -> r) P -> r = new Node();
	mid = (lo + hi)/2;
	if ( P -> Has == 1) {
		P -> l -> Has = 1;
		P -> r -> Has = 1;
		P -> Has = 0;
		P -> l -> Max = P -> Max;
		P -> r -> Max = P -> Max;
	}
	Find(P -> l, lo, mid, st, fn);
	Find(P -> r, mid + 1, hi, st, fn);
	P -> Max = max ( P -> l -> Max, P -> r -> Max);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans, s, sum, x, y, r, p, i, j;
	
	cin >> n;
	
	vector < pair < ll, ll > > v;
	Node *Tre = new Node();
	for (i = 1; i <= n; i ++) {
		cin >> x >> y;
		v.push_back(make_pair(x, y));
	}
	ans= 0;
	v.push_back(make_pair(0, 0));
	sort(v.begin(), v.end());
	for (i =1; i < v.size(); i ++)  {
		s = v[i].second - (v[i].first - v[i - 1].first);
		Change(Tre, 1, n, 1, i - 1, ll((v[i - 1].first -v[i].first)));
		Change(Tre, 1, n, 1, i, (v[i].second));
		ans = max (ans, Tre -> Max);
	}
	cout << ans << endl;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:67:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (i =1; i < v.size(); i ++)  {
      |             ~~^~~~~~~~~~
art.cpp:54:5: warning: unused variable 't' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |     ^
art.cpp:54:11: warning: unused variable 'm' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |           ^
art.cpp:54:19: warning: variable 's' set but not used [-Wunused-but-set-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                   ^
art.cpp:54:22: warning: unused variable 'sum' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                      ^~~
art.cpp:54:33: warning: unused variable 'r' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                                 ^
art.cpp:54:36: warning: unused variable 'p' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                                    ^
art.cpp:54:42: warning: unused variable 'j' [-Wunused-variable]
   54 |  ll t, n, m, ans, s, sum, x, y, r, p, i, j;
      |                                          ^
art.cpp: In function 'll Find(Node*, ll, ll, ll, ll)':
art.cpp:48:11: warning: control reaches end of non-void function [-Wreturn-type]
   48 |  P -> Max = max ( P -> l -> Max, P -> r -> Max);
      |  ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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