oj.uz

Submission #720150

# Submission time Handle Problem Language Result Execution time Memory
720150 2023-04-07T13:55:59 Z marvinthang Distributing Candies (IOI21_candies) C++17
100 / 100
 1470 ms 44576 KB 
/*************************************
*    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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 7 ms 692 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 42716 KB Output is correct
2 Correct 1420 ms 41948 KB Output is correct
3 Correct 1433 ms 41780 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 235 ms 31356 KB Output is correct
3 Correct 437 ms 9776 KB Output is correct
4 Correct 1339 ms 43788 KB Output is correct
5 Correct 1257 ms 44256 KB Output is correct
6 Correct 1470 ms 44576 KB Output is correct
7 Correct 1337 ms 43912 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 123 ms 29740 KB Output is correct
4 Correct 392 ms 8848 KB Output is correct
5 Correct 1092 ms 37492 KB Output is correct
6 Correct 1038 ms 38212 KB Output is correct
7 Correct 1059 ms 38768 KB Output is correct
8 Correct 1101 ms 37400 KB Output is correct
9 Correct 1094 ms 38876 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 7 ms 692 KB Output is correct
6 Correct 1422 ms 42716 KB Output is correct
7 Correct 1420 ms 41948 KB Output is correct
8 Correct 1433 ms 41780 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 235 ms 31356 KB Output is correct
11 Correct 437 ms 9776 KB Output is correct
12 Correct 1339 ms 43788 KB Output is correct
13 Correct 1257 ms 44256 KB Output is correct
14 Correct 1470 ms 44576 KB Output is correct
15 Correct 1337 ms 43912 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 123 ms 29740 KB Output is correct
19 Correct 392 ms 8848 KB Output is correct
20 Correct 1092 ms 37492 KB Output is correct
21 Correct 1038 ms 38212 KB Output is correct
22 Correct 1059 ms 38768 KB Output is correct
23 Correct 1101 ms 37400 KB Output is correct
24 Correct 1094 ms 38876 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 359 ms 8880 KB Output is correct
27 Correct 216 ms 30924 KB Output is correct
28 Correct 1368 ms 42544 KB Output is correct
29 Correct 1353 ms 42892 KB Output is correct
30 Correct 1423 ms 43012 KB Output is correct
31 Correct 1415 ms 43312 KB Output is correct
32 Correct 1332 ms 43472 KB Output is correct