Submission #681411

#	Time	Username	Problem	Language	Result	Execution time	Memory
681411		GusterGoose27	Potatoes and fertilizers (LMIO19_bulves)	C++11	Compilation error	0 ms	0 KiB

bulves

#include <bits/stdc++.h>

using namespace std;

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

#define int long long;

const int MAXN = 5e5;
const ll inf = 1e18;
int n;
int vals[MAXN];
ll pre[MAXN];
int ben[MAXN];

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	pii mx;
	int lz = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
			mx = max(l->mx, r->mx);
		}
		else {
			mx = pii(ben[lp], lp);
		}
	}
	void add_to(int v) {
		lz += v;
		mx.first += v;
	}
	void push() {
		if (l) {
			l->add_to(lz);
			r->add_to(lz);
		}
		lz = 0;
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			return add_to(v);
		}
		push();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mx = max(l->mx, r->mx);
	}
	pii get_mx(int lv, int rv) {
		if (lp > rv || rp < lv) return pii(-1, -1);
		if (lp >= lv && rp <= rv) return mx;
		push();
		return max(l->get_mx(lv, rv), r->get_mx(lv, rv));
	}
};

stree *mx_tree;

class stree2 {
public:
	int lp, rp;
	stree2 *l = nullptr;
	stree2 *r = nullptr;
	ll mn;
	ll sub = 0;
	stree2(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int m = (lp+rp)/2;
			l = new stree2(lp, m);
			r = new stree2(m+1, rp);
			mn = min(l->mn, r->mn);
		}
		else {
			if (pre[lp] <= 0) mn = inf;
			else mn = pre[lp];
		}
	}
	void erase() {
		if (mn) return;
		if (lp == rp) {
			mn = inf;
			mx_tree->upd(0, lp, -2);
			return;
		}
		push();
		l->erase();
		r->erase();
		mn = min(l->mn, r->mn);
	}
	void add_to(int v) {
		mn += v;
		sub += v;
		if (mn == 0) {
			erase();
		}
	}
	void push() {
		if (l) {
			l->add_to(sub);
			r->add_to(sub);
		}
		sub = 0;
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			add_to(v);
			return;
		}
		push();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mn = min(l->mn, r->mn);
	}
	ll query(int lv, int rv) {
		if (lp > rv || rp < lv) return inf;
		if (lp >= lv && rp <= rv) return mn;
		push();
		return min(l->query(lv, rv), r->query(lv, rv));
	}
};

stree2 *beat_tree;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		vals[i] = x-y;
		pre[i] += vals[i];
		if (i < n-1) pre[i+1] = pre[i];
		ans += (pre[i] < 0) ? (-pre[i]) : pre[i];
	}
	for (int i = n-1; i >= 0; i--) {
		if (pre[i] <= 0) ben[i]--;
		else ben[i]++;
		if (i) ben[i-1] = ben[i];
	}
	mx_tree = new stree(0, n-1);
	beat_tree = new stree2(0, n-1);
	pii bst = mx_tree->get_mx(0, n-1);
	ll rem = pre[n-1];
	while (bst.first && rem) {
		ll lim = beat_tree->query(bst.second, n-1);
		lim = min(lim, rem);
		ans -= lim*bst.first;
		beat_tree->upd(bst.second, n-1, -lim);
		bst = mx_tree->get_mx(0, n-1);
		rem -= lim;
	}
	cout << ans << "\n";
}

Compilation message (stderr)

bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:10:7: note: in expansion of macro 'int'
   10 | const int MAXN = 5e5;
      |       ^~~
bulves.cpp:10:11: error: 'MAXN' does not name a type
   10 | const int MAXN = 5e5;
      |           ^~~~
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:12:1: note: in expansion of macro 'int'
   12 | int n;
      | ^~~
bulves.cpp:12:5: error: 'n' does not name a type; did you mean 'yn'?
   12 | int n;
      |     ^
      |     yn
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:13:1: note: in expansion of macro 'int'
   13 | int vals[MAXN];
      | ^~~
bulves.cpp:13:5: error: 'vals' does not name a type
   13 | int vals[MAXN];
      |     ^~~~
bulves.cpp:14:8: error: 'MAXN' was not declared in this scope
   14 | ll pre[MAXN];
      |        ^~~~
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:15:1: note: in expansion of macro 'int'
   15 | int ben[MAXN];
      | ^~~
bulves.cpp:15:5: error: 'ben' does not name a type; did you mean 'mblen'?
   15 | int ben[MAXN];
      |     ^~~
      |     mblen
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:19:2: note: in expansion of macro 'int'
   19 |  int lp, rp;
      |  ^~~
bulves.cpp:19:6: error: 'lp' does not name a type; did you mean 'll'?
   19 |  int lp, rp;
      |      ^~
      |      ll
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:23:2: note: in expansion of macro 'int'
   23 |  int lz = 0;
      |  ^~~
bulves.cpp:23:6: error: 'lz' does not name a type; did you mean 'll'?
   23 |  int lz = 0;
      |      ^~
      |      ll
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:24:8: note: in expansion of macro 'int'
   24 |  stree(int lv, int rv) {
      |        ^~~
bulves.cpp:24:7: note: to match this '('
   24 |  stree(int lv, int rv) {
      |       ^
bulves.cpp:24:12: error: 'lv' does not name a type; did you mean 'll'?
   24 |  stree(int lv, int rv) {
      |            ^~
      |            ll
bulves.cpp:24:20: error: 'rv' does not name a type
   24 |  stree(int lv, int rv) {
      |                    ^~
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:37:14: note: in expansion of macro 'int'
   37 |  void add_to(int v) {
      |              ^~~
bulves.cpp:37:13: note: to match this '('
   37 |  void add_to(int v) {
      |             ^
bulves.cpp:37:18: error: 'v' does not name a type
   37 |  void add_to(int v) {
      |                  ^
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:48:11: note: in expansion of macro 'int'
   48 |  void upd(int lv, int rv, int v) {
      |           ^~~
bulves.cpp:48:10: note: to match this '('
   48 |  void upd(int lv, int rv, int v) {
      |          ^
bulves.cpp:48:15: error: 'lv' does not name a type; did you mean 'll'?
   48 |  void upd(int lv, int rv, int v) {
      |               ^~
      |               ll
bulves.cpp:48:23: error: 'rv' does not name a type
   48 |  void upd(int lv, int rv, int v) {
      |                       ^~
bulves.cpp:48:31: error: 'v' does not name a type
   48 |  void upd(int lv, int rv, int v) {
      |                               ^
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:58:13: note: in expansion of macro 'int'
   58 |  pii get_mx(int lv, int rv) {
      |             ^~~
bulves.cpp:58:12: note: to match this '('
   58 |  pii get_mx(int lv, int rv) {
      |            ^
bulves.cpp:58:17: error: 'lv' does not name a type; did you mean 'll'?
   58 |  pii get_mx(int lv, int rv) {
      |                 ^~
      |                 ll
bulves.cpp:58:25: error: 'rv' does not name a type
   58 |  pii get_mx(int lv, int rv) {
      |                         ^~
bulves.cpp: In member function 'void stree::push()':
bulves.cpp:43:14: error: 'lz' was not declared in this scope; did you mean 'l'?
   43 |    l->add_to(lz);
      |              ^~
      |              l
bulves.cpp:46:3: error: 'lz' was not declared in this scope; did you mean 'l'?
   46 |   lz = 0;
      |   ^~
      |   l
bulves.cpp: At global scope:
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:70:2: note: in expansion of macro 'int'
   70 |  int lp, rp;
      |  ^~~
bulves.cpp:70:6: error: 'lp' does not name a type; did you mean 'll'?
   70 |  int lp, rp;
      |      ^~
      |      ll
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:75:9: note: in expansion of macro 'int'
   75 |  stree2(int lv, int rv) {
      |         ^~~
bulves.cpp:75:8: note: to match this '('
   75 |  stree2(int lv, int rv) {
      |        ^
bulves.cpp:75:13: error: 'lv' does not name a type; did you mean 'll'?
   75 |  stree2(int lv, int rv) {
      |             ^~
      |             ll
bulves.cpp:75:21: error: 'rv' does not name a type
   75 |  stree2(int lv, int rv) {
      |                     ^~
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:101:14: note: in expansion of macro 'int'
  101 |  void add_to(int v) {
      |              ^~~
bulves.cpp:101:13: note: to match this '('
  101 |  void add_to(int v) {
      |             ^
bulves.cpp:101:18: error: 'v' does not name a type
  101 |  void add_to(int v) {
      |                  ^
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:115:11: note: in expansion of macro 'int'
  115 |  void upd(int lv, int rv, int v) {
      |           ^~~
bulves.cpp:115:10: note: to match this '('
  115 |  void upd(int lv, int rv, int v) {
      |          ^
bulves.cpp:115:15: error: 'lv' does not name a type; did you mean 'll'?
  115 |  void upd(int lv, int rv, int v) {
      |               ^~
      |               ll
bulves.cpp:115:23: error: 'rv' does not name a type
  115 |  void upd(int lv, int rv, int v) {
      |                       ^~
bulves.cpp:115:31: error: 'v' does not name a type
  115 |  void upd(int lv, int rv, int v) {
      |                               ^
bulves.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
bulves.cpp:126:11: note: in expansion of macro 'int'
  126 |  ll query(int lv, int rv) {
      |           ^~~
bulves.cpp:126:10: note: to match this '('
  126 |  ll query(int lv, int rv) {
      |          ^
bulves.cpp:126:15: error: 'lv' does not name a type; did you mean 'll'?
  126 |  ll query(int lv, int rv) {
      |               ^~
      |               ll
bulves.cpp:126:23: error: 'rv' does not name a type
  126 |  ll query(int lv, int rv) {
      |                       ^~
bulves.cpp: In member function 'void stree2::erase()':
bulves.cpp:91:7: error: 'lp' was not declared in this scope; did you mean 'l'?
   91 |   if (lp == rp) {
      |       ^~
      |       l
bulves.cpp:91:13: error: 'rp' was not declared in this scope; did you mean 'r'?
   91 |   if (lp == rp) {
      |             ^~
      |             r
bulves.cpp: In function 'int main()':
bulves.cpp:138:9: error: 'n' was not declared in this scope; did you mean 'yn'?
  138 |  cin >> n;
      |         ^
      |         yn
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:140:7: note: in expansion of macro 'int'
  140 |  for (int i = 0; i < n; i++) {
      |       ^~~
bulves.cpp:140:11: error: 'i' was not declared in this scope
  140 |  for (int i = 0; i < n; i++) {
      |           ^
bulves.cpp:140:23: error: expected ')' before ';' token
  140 |  for (int i = 0; i < n; i++) {
      |      ~                ^
      |                       )
bulves.cpp:140:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  140 |  for (int i = 0; i < n; i++) {
      |  ^~~
bulves.cpp:140:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  140 |  for (int i = 0; i < n; i++) {
      |                         ^
bulves.cpp:140:25: error: 'i' was not declared in this scope
bulves.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
bulves.cpp:147:7: note: in expansion of macro 'int'
  147 |  for (int i = n-1; i >= 0; i--) {
      |       ^~~
bulves.cpp:147:26: error: expected ')' before ';' token
  147 |  for (int i = n-1; i >= 0; i--) {
      |      ~                   ^
      |                          )
bulves.cpp:147:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  147 |  for (int i = n-1; i >= 0; i--) {
      |  ^~~
bulves.cpp:147:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  147 |  for (int i = n-1; i >= 0; i--) {
      |                            ^
bulves.cpp:155:11: error: 'pre' was not declared in this scope
  155 |  ll rem = pre[n-1];
      |           ^~~