Submission #720150

#	Time	Username	Problem	Language	Result	Execution time	Memory
720150		marvinthang	Distributing Candies (IOI21_candies)	C++17	100 / 100	1470 ms	44576 KiB

candies

/*************************************
*    author: marvinthang             *
*    created: 15.10.2022 08:23:32    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const long long oo = 1e18;

struct Node {
	long long mi, ma, lazy;
	Node(): mi(oo), ma(-oo), lazy(0) {}
	Node(long long a, long long b, long long c): ma(a), mi(b), lazy(c) {}
	Node operator + (const Node &other) const {
		return Node(max(ma, other.ma), min(mi, other.mi), 0);
	}
};
struct SegmentTree {
	int n;
	vector <Node> st;
	void add(int i, long long val) {
		st[i].ma += val;
		st[i].mi += val;
		st[i].lazy += val; 
	}
	SegmentTree(int n = 0): n(n), st(n << 2, Node(0, 0, 0)) {}
	void pushDown(int i) {
		if (!st[i].lazy) return;
		add(i << 1, st[i].lazy);
		add(i << 1 | 1, st[i].lazy);
		st[i].lazy = 0;
		return;
	}
	void update(int i, int l, int r, int u, int v, long long val) {
		if (l > v || r < u) return;
		if (u <= l && r <= v) {
			add(i, val);
			return;
		}
		pushDown(i);
		int m = l + r >> 1;
		update(i << 1, l, m, u, v, val);
		update(i << 1 | 1, m + 1, r, u, v, val);
		st[i] = st[i << 1] + st[i << 1 | 1];
	}
	void update(int l, int r, long long val) { update(1, 0, n, l, r, val); }
	Node get(int i, int l, int r, int u, int v) {
		if (l > v || r < u) return Node();
		if (u <= l && r <= v) return st[i];
		int m = l + r >> 1;
		pushDown(i);
		return get(i << 1, l, m, u, v) + get(i << 1 | 1, m + 1, r, u, v);
	}
	Node get(int l, int r) { return get(1, 0, n, l, r); }
};

vector <int> distribute_candies(vector <int> c, vector <int> ql, vector <int> qr, vector <int> qv) {
	int n = c.size(), q = ql.size();
	vector <vector <pair <int, int>>> events(n + 1);
	for (int i = 0; i < q; ++i) {
		events[ql[i]].push_back(make_pair(i, qv[i]));
		events[qr[i] + 1].push_back(make_pair(i, -qv[i]));
	}
	vector <int> res(n);
	SegmentTree st(q);
	for (int i = 0; i < n; ++i) {
		for (auto [p, v]: events[i]) st.update(p + 1, q, v);
		int l = 0, r = q;
		while (l <= r) {
			int m = l + r >> 1;
			Node cc = st.get(m, q);
			if (cc.ma - cc.mi > c[i]) l = m + 1;
			else r = m - 1;
		}
		if (r == -1) res[i] = st.get(q, q).ma - st.get(0, q).mi;
		else {
			if (st.get(r, r).ma == st.get(r, q).mi) res[i] = c[i] - (st.get(r, q).ma - st.get(q, q).ma);
			else res[i] = st.get(q, q).mi - st.get(r, q).mi;
		}
	}
	return res;
}

Compilation message (stderr)

candies.cpp: In constructor 'Node::Node(long long int, long long int, long long int)':
candies.cpp:34:16: warning: 'Node::ma' will be initialized after [-Wreorder]
   34 |  long long mi, ma, lazy;
      |                ^~
candies.cpp:34:12: warning:   'long long int Node::mi' [-Wreorder]
   34 |  long long mi, ma, lazy;
      |            ^~
candies.cpp:36:2: warning:   when initialized here [-Wreorder]
   36 |  Node(long long a, long long b, long long c): ma(a), mi(b), lazy(c) {}
      |  ^~~~
candies.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, long long int)':
candies.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int m = l + r >> 1;
      |           ~~^~~
candies.cpp: In member function 'Node SegmentTree::get(int, int, int, int, int)':
candies.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int m = l + r >> 1;
      |           ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:93:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |    int m = l + r >> 1;
      |            ~~^~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33