Submission #499317

#	Time	Username	Problem	Language	Result	Execution time	Memory
499317		hollwo_pelw	Food Court (JOI21_foodcourt)	C++17	100 / 100	460 ms	66796 KiB

foodcourt

/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

const int N = 2.5e5 + 5;

#define int long long

vector<pair<int, int>> supd[N], fupd[N], qry[N];
int n, m, q, color[N], res[N];

// segment tree
struct node_t {
	int mx, sum;
	node_t (int _mx = 0, int _sum = 0)
		: mx(_mx), sum(_sum) {}
	friend node_t merge(const node_t &a, const node_t &b) {
		return node_t(max(a.mx + b.sum, b.mx), a.sum + b.sum);
	}
} st[N << 2];

#define tm (tl + tr >> 1)
#define left id << 1, tl, tm
#define right id << 1 | 1, tm + 1, tr

void update_st(int p, int v, int id = 1, int tl = 1, int tr = q) {
	if (tl == tr)
		return st[id] = node_t(max(0ll, v), v), (void) 0;
	(p > tm ? update_st(p, v, right)
			: update_st(p, v, left));
	st[id] = merge(st[id << 1], st[id << 1 | 1]);
}

node_t query_st(int l, int r, int id = 1, int tl = 1, int tr = q) {
	if (l > tr || tl > r) return node_t();
	if (l <= tl && tr <= r) return st[id];
	return merge(query_st(l, r, left), query_st(l, r, right));
}

// fenwick tree
int bit[N];
inline void update_fw(int p, int v) {
	for (; p < N; p += p & -p)
		bit[p] += v;
}

inline int query_fw(int p) {
	int r = 0;
	for (; p > 0; p -= p & -p)
		r += bit[p];
	return r;
}

inline int find_kth(int val) {
	int p = 0;
	for (int i = 17; ~i; i--) {
		if (p + (1 << i) < N && bit[p + (1 << i)] < val) {
			p += 1 << i;
			val -= bit[p];
		}
	}
	return p + 1;
}

void Hollwo_Pelw() {
	cin >> n >> m >> q;

	for (int i = 1, t, l, r, k; i <= q; i++) {
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> color[i] >> k;
			supd[l    ].emplace_back(i, +k);
			supd[r + 1].emplace_back(i,  0);
			fupd[l    ].emplace_back(i, +k);
			fupd[r + 1].emplace_back(i, -k);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			supd[l    ].emplace_back(i, -k);
			supd[r + 1].emplace_back(i,  0);
		}
		if (t == 3) {
			cin >> l >> k;
			qry[l].emplace_back(i, k);
		}
	}

	memset(res, -1, sizeof res);

	for (int i = 1; i <= n; i++) {
		for (auto [p, v] : supd[i])
			update_st(p, v);
		for (auto [p, v] : fupd[i])
			update_fw(p, v);
		for (auto [p, v] : qry[i]) {
			auto cur_state = query_st(1, p);

			if (v > cur_state.mx) {
				res[p] = 0;
			} else {
				v = query_fw(p) - (cur_state.mx - v);
				res[p] = color[find_kth(v)];
			}
		}
	}

	for (int i = 1; i <= q; i++)
		if (~res[i]) cout << res[i] << '\n';
}

Compilation message (stderr)

foodcourt.cpp: In function 'void update_st(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
foodcourt.cpp:73:7: note: in expansion of macro 'tm'
   73 |  (p > tm ? update_st(p, v, right)
      |       ^~
foodcourt.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
foodcourt.cpp:68:28: note: in expansion of macro 'tm'
   68 | #define right id << 1 | 1, tm + 1, tr
      |                            ^~
foodcourt.cpp:73:28: note: in expansion of macro 'right'
   73 |  (p > tm ? update_st(p, v, right)
      |                            ^~~~~
foodcourt.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
foodcourt.cpp:67:27: note: in expansion of macro 'tm'
   67 | #define left id << 1, tl, tm
      |                           ^~
foodcourt.cpp:74:22: note: in expansion of macro 'left'
   74 |    : update_st(p, v, left));
      |                      ^~~~
foodcourt.cpp: In function 'node_t query_st(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
foodcourt.cpp:67:27: note: in expansion of macro 'tm'
   67 | #define left id << 1, tl, tm
      |                           ^~
foodcourt.cpp:81:30: note: in expansion of macro 'left'
   81 |  return merge(query_st(l, r, left), query_st(l, r, right));
      |                              ^~~~
foodcourt.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
foodcourt.cpp:68:28: note: in expansion of macro 'tm'
   68 | #define right id << 1 | 1, tm + 1, tr
      |                            ^~
foodcourt.cpp:81:52: note: in expansion of macro 'right'
   81 |  return merge(query_st(l, r, left), query_st(l, r, right));
      |                                                    ^~~~~
foodcourt.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
foodcourt.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11