oj.uz

Submission #436898

# Submission time Handle Problem Language Result Execution time Memory
436898 2021-06-25T07:59:40 Z maomao90 Distributing Candies (IOI21_candies) C++17
100 / 100
 796 ms 37956 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(x) x.begin(), x.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 200005

int n, q;
vi c;
vi ans;
vi qs[MAXN], qe[MAXN];

#define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
ll mx[MAXN * 4], mn[MAXN * 4], lazy[MAXN * 4];
void propo(int u, int lo, int hi) {
	if (lazy[u] == 0 || lo == hi) return;
	MLR;
	mx[lc] += lazy[u];
	mn[lc] += lazy[u];
	mx[rc] += lazy[u];
	mn[rc] += lazy[u];
	lazy[lc] += lazy[u];
	lazy[rc] += lazy[u];
	lazy[u] = 0;
}
void incre(int s, int e, int x, int u, int lo, int hi) {
	if (lo >= s && hi <= e) {
		lazy[u] += x;
		mn[u] += x;
		mx[u] += x;
		return;
	}
	propo(u, lo, hi);
	MLR;
	if (s <= mid) incre(s, e, x, lc, lo, mid);
	if (e > mid) incre(s, e, x, rc, mid + 1, hi);
	mn[u] = min(mn[lc], mn[rc]);
	mx[u] = max(mx[lc], mx[rc]);
}
void incre(int s, int e, int x) {
	incre(s, e, x, 1, 0, q);
}
ll getmax(int s, int e, int u, int lo, int hi) {
	if (lo >= s && hi <= e) {
		return mx[u];
	}
	propo(u, lo, hi);
	MLR;
	if (e <= mid) return getmax(s, e, lc, lo, mid);
	else if (s > mid) return getmax(s, e, rc, mid + 1, hi);
	else return max(getmax(s, e, lc, lo, mid), getmax(s, e, rc, mid + 1, hi));
}
ll getmax(int s, int e) {
	return getmax(s, e, 1, 0, q);
}
ll getmin(int s, int e, int u, int lo, int hi) {
	if (lo >= s && hi <= e) {
		return mn[u];
	}
	propo(u, lo, hi);
	MLR;
	if (e <= mid) return getmin(s, e, lc, lo, mid);
	else if (s > mid) return getmin(s, e, rc, mid + 1, hi);
	else return min(getmin(s, e, lc, lo, mid), getmin(s, e, rc, mid + 1, hi));

}
ll getmin(int s, int e) {
	return getmin(s, e, 1, 0, q);
}
int upper(int x, ll pmn, ll pmx, int u, int lo, int hi) {
	if (lo == hi) {
		return lo;
	}
	propo(u, lo, hi);
	MLR;
	ll npmn = min(pmn, mn[rc]), npmx = max(pmx, mx[rc]);
	if (npmx - npmn > x) {
		return upper(x, pmn, pmx, rc, mid + 1, hi);
	} else {
		return upper(x, npmn, npmx, lc, lo, mid);
	}
}
int upper(int s, ll pmn, ll pmx) {
	return upper(s, pmn, pmx, 1, 0, q);
}

vi distribute_candies(vi c, vi l, vi r, vi v) {
	::c = c;
	n = c.size(); q = l.size();
	l.insert(l.begin(), 0);
	r.insert(r.begin(), 0);
	v.insert(v.begin(), 0);
	REP (i, 1, q + 1) {
		qs[l[i]].pb(i);
		qe[r[i]].pb(i);
	}
	ans.resize(n);
	REP (i, 0, n) {
		for (int &j : qs[i]) {
			incre(j, q, v[j]);
			debug(" incre %d %d: %d\n", j, q, v[j]);
		}
		ll sum = getmax(q, q);
		debug("%lld %lld %lld\n", sum, mx[1], mn[1]);
		if (mx[1] - mn[1] <= c[i]) {
			ans[i] = sum - mn[1];
		} else {
			int id = upper(c[i], LINF, -LINF);
			ll cur = getmax(id, id);
			ll mn = getmin(id + 1, q);
			ll mx = getmax(id + 1, q);
			debug(" %d %lld %lld %lld\n", id, cur, mn, mx);
			if (cur < mn) {
				ans[i] = sum - (mx - c[i]);
			} else {
				ans[i] = sum - mn;
			}
		}
		for (int &j : qe[i]) {
			incre(j, q, -v[j]);
			debug(" decre %d %d: %d\n", j, q, -v[j]);
		}
	}
	return ans;
}

Compilation message

candies.cpp: In function 'void propo(int, int, int)':
candies.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
candies.cpp:50:2: note: in expansion of macro 'MLR'
   50 |  MLR;
      |  ^~~
candies.cpp:46:17: warning: unused variable 'mid' [-Wunused-variable]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                 ^~~
candies.cpp:50:2: note: in expansion of macro 'MLR'
   50 |  MLR;
      |  ^~~
candies.cpp: In function 'void incre(int, int, int, int, int, int)':
candies.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
candies.cpp:67:2: note: in expansion of macro 'MLR'
   67 |  MLR;
      |  ^~~
candies.cpp: In function 'll getmax(int, int, int, int, int)':
candies.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
candies.cpp:81:2: note: in expansion of macro 'MLR'
   81 |  MLR;
      |  ^~~
candies.cpp: In function 'll getmin(int, int, int, int, int)':
candies.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
candies.cpp:94:2: note: in expansion of macro 'MLR'
   94 |  MLR;
      |  ^~~
candies.cpp: In function 'int upper(int, ll, ll, int, int, int)':
candies.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
candies.cpp:108:2: note: in expansion of macro 'MLR'
  108 |  MLR;
      |  ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9612 KB Output is correct
2 Correct 8 ms 9676 KB Output is correct
3 Correct 10 ms 9804 KB Output is correct
4 Correct 10 ms 9804 KB Output is correct
5 Correct 12 ms 9932 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 37824 KB Output is correct
2 Correct 720 ms 37948 KB Output is correct
3 Correct 755 ms 37876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 343 ms 29532 KB Output is correct
3 Correct 132 ms 15000 KB Output is correct
4 Correct 773 ms 37868 KB Output is correct
5 Correct 707 ms 37780 KB Output is correct
6 Correct 700 ms 37912 KB Output is correct
7 Correct 796 ms 37844 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9676 KB Output is correct
2 Correct 11 ms 9620 KB Output is correct
3 Correct 191 ms 29696 KB Output is correct
4 Correct 106 ms 13916 KB Output is correct
5 Correct 309 ms 32148 KB Output is correct
6 Correct 354 ms 32192 KB Output is correct
7 Correct 340 ms 32232 KB Output is correct
8 Correct 322 ms 32148 KB Output is correct
9 Correct 369 ms 32156 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9612 KB Output is correct
2 Correct 8 ms 9676 KB Output is correct
3 Correct 10 ms 9804 KB Output is correct
4 Correct 10 ms 9804 KB Output is correct
5 Correct 12 ms 9932 KB Output is correct
6 Correct 749 ms 37824 KB Output is correct
7 Correct 720 ms 37948 KB Output is correct
8 Correct 755 ms 37876 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 343 ms 29532 KB Output is correct
11 Correct 132 ms 15000 KB Output is correct
12 Correct 773 ms 37868 KB Output is correct
13 Correct 707 ms 37780 KB Output is correct
14 Correct 700 ms 37912 KB Output is correct
15 Correct 796 ms 37844 KB Output is correct
16 Correct 9 ms 9676 KB Output is correct
17 Correct 11 ms 9620 KB Output is correct
18 Correct 191 ms 29696 KB Output is correct
19 Correct 106 ms 13916 KB Output is correct
20 Correct 309 ms 32148 KB Output is correct
21 Correct 354 ms 32192 KB Output is correct
22 Correct 340 ms 32232 KB Output is correct
23 Correct 322 ms 32148 KB Output is correct
24 Correct 369 ms 32156 KB Output is correct
25 Correct 7 ms 9676 KB Output is correct
26 Correct 107 ms 13892 KB Output is correct
27 Correct 350 ms 29600 KB Output is correct
28 Correct 682 ms 37768 KB Output is correct
29 Correct 716 ms 37780 KB Output is correct
30 Correct 689 ms 37812 KB Output is correct
31 Correct 769 ms 37816 KB Output is correct
32 Correct 761 ms 37956 KB Output is correct