oj.uz

Submission #590757

# Submission time Handle Problem Language Result Execution time Memory
590757 2022-07-06T10:22:56 Z Bungmint Examination (JOI19_examination) C++17
100 / 100
 585 ms 26164 KB 
// Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
	return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
	os << '{';
	string sep;
	for (const T &x : v)
		os << sep << x, sep = ", ";
	return os << '}';
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
	os << vector<T>(all(v));
	return os;
}
template <typename T, typename S, typename C>
ostream &operator<<(ostream &os, priority_queue<T, S, C> pq) {
	vector<T> v;
	while (sz(pq)) {
		v.pb(pq.top());
		pq.pop();
	}
	os << v;
	return os;
}
void dbg_out()
{
	cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
	cerr << ' ' << H;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "\033[1;35m" << __func__ << ':' << __LINE__ << " (" << #__VA_ARGS__ << "):\033[33m", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda
{
	template <typename Fun>
	struct y_combinator_result
	{
		Fun fun_;
		template <typename T>
		explicit y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		decltype(auto) operator()(Args &&...args)
		{
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun)
	{
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

inline namespace Range {
	class ForwardRange {
		int src, dst;

	  public:
	  	explicit constexpr ForwardRange(const int l, const int r) : src(l), dst(r) {}
		explicit constexpr ForwardRange(const int n) : src(0), dst(n) {}
		constexpr ForwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src < dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return src++; }
	};
	class BackwardRange {
		int src, dst;

	  public:
	  	explicit constexpr BackwardRange(const int l, const int r) : src(r), dst(l) {}
		explicit constexpr BackwardRange(const int n) : src(n), dst(0) {}
		constexpr BackwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src > dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return --src; }
	};
	using rep = ForwardRange;
	using per = BackwardRange;
};

/**
 * Description: point update and rectangle sum with offline 2D BIT. 
	* For each of the points to be updated, $x\in (0,SZ)$ and $y\neq 0$.
 * Time: O(N\log^2 N)
 * Memory: O(N\log N)
 * Source: Benq
 * Verification: 
 	* https://dmoj.ca/problem/occ19g4
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=722 (753 ms)
 	* http://www.usaco.org/index.php?page=viewproblem2&cpid=601 (679 ms)
 */

template<class T, int SZ> struct BITOff2D { 
	bool mode = 0; // mode = 1 -> initialized
	vpi todo; // locations of updates to process
	int cnt[SZ], st[SZ];
	vi val; vector<T> bit; // store all BITs in single vector
	void init() { assert(!mode); mode = 1;
		int lst[SZ]; for (int i : rep(SZ)) lst[i] = cnt[i] = 0;
		sort(all(todo),[](const pii& a, const pii& b) { 
			return a.se < b.se; });
		for (auto &t : todo) for (int x = t.fi; x < SZ; x += x & -x) 
			if (lst[x] != t.se) lst[x] = t.se, cnt[x]++;
		int sum = 0; for (int i : rep(SZ)) lst[i] = 0, st[i] = (sum += cnt[i]);
		val.resize(sum); bit.resize(sum); reverse(all(todo));
		for (auto &t : todo) for (int x = t.fi; x < SZ; x += x & -x) 
			if (lst[x] != t.se) lst[x] = t.se, val[--st[x]] = t.se;
	}
	int rank(int y, int l, int r) {
		return ub(begin(val) + l, begin(val) + r, y) - begin(val) - l; }
	void UPD(int x, int y, T t) {
		for (y = rank(y, st[x], st[x] + cnt[x]); y <= cnt[x]; y += y & -y) 
			bit[st[x] + y - 1] += t; }
	void upd(int x, int y, T t) { 
		if (!mode) todo.pb({x, y});
		else for (; x < SZ; x += x & -x) UPD(x, y, t); }
	int QUERY(int x, int y) { T res = 0;
		for (y = rank(y, st[x], st[x] + cnt[x]); y; y -= y & -y) res += bit[st[x] + y - 1];
		return res; }
	T query(int x, int y) { assert(mode);
		T res = 0; for (; x; x -= x & -x) res += QUERY(x, y);
		return res; }
	T query(int xl, int xr, int yl, int yr) { 
		return query(xr, yr) - query(xl - 1, yr)
			- query(xr, yl - 1) + query(xl - 1, yl - 1); }
};
BITOff2D<int, 210000> bit;

void solve()
{
	int n, q;
	cin >> n >> q;
	vpi sorted_by_sum(n);
	vector<ar<int, 3>> queries(q);
	vi ind(q), ans(q), xs(n), ys(n);
	for (int i : rep(n)) {
		int s, t;
		cin >> s >> t;
		sorted_by_sum[i] = {s, t};
		xs[i] = s;
		ys[i] = t;
		// bit.upd(s, t, 1);
	}
	sort(all(sorted_by_sum), [&](auto x, auto y){
		return x.fi + x.se > y.fi + y.se;
	});
	for (int i : rep(q)) {
		auto &[x, y, z] = queries[i];
		cin >> x >> y >> z;
		xs.pb(x), ys.pb(y);
	}
	iota(all(ind), 0);
	sort(all(ind), [&](int i, int j){
		return queries[i][2] > queries[j][2];
	});
	sort(all(xs)), xs.resize(unique(all(xs)) - xs.begin());
	sort(all(ys)), ys.resize(unique(all(ys)) - ys.begin());
	for (auto &[s, t] : sorted_by_sum) {
		s = lb(all(xs), s) - xs.begin() + 1;
		t = lb(all(ys), t) - ys.begin() + 1;
		bit.upd(s, t, 0);
	}
	bit.init();
	int ptr{};
	for (int i : rep(q)) {
		auto& [x, y, z] = queries[ind[i]];
		x = lb(all(xs), x) - xs.begin() + 1;
		y = lb(all(ys), y) - ys.begin() + 1;
		while (ptr < n && xs[sorted_by_sum[ptr].fi - 1] + ys[sorted_by_sum[ptr].se - 1] >= z) {
			auto [s, t] = sorted_by_sum[ptr++];
			bit.upd(s, t, 1);
		}
		ans[ind[i]] = bit.query(x, sz(xs), y, sz(ys));
	}
	for (int i : rep(q)) cout << ans[i] << '\n';
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
	{
		solve();
	}
#ifdef LOCAL
	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 13 ms 3316 KB Output is correct
8 Correct 11 ms 3424 KB Output is correct
9 Correct 13 ms 3416 KB Output is correct
10 Correct 7 ms 3156 KB Output is correct
11 Correct 10 ms 3404 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 10 ms 3336 KB Output is correct
14 Correct 10 ms 3384 KB Output is correct
15 Correct 10 ms 3368 KB Output is correct
16 Correct 7 ms 3464 KB Output is correct
17 Correct 8 ms 3164 KB Output is correct
18 Correct 4 ms 3028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 18704 KB Output is correct
2 Correct 456 ms 18636 KB Output is correct
3 Correct 457 ms 18656 KB Output is correct
4 Correct 175 ms 12472 KB Output is correct
5 Correct 272 ms 19216 KB Output is correct
6 Correct 104 ms 9920 KB Output is correct
7 Correct 335 ms 18416 KB Output is correct
8 Correct 365 ms 18636 KB Output is correct
9 Correct 333 ms 18316 KB Output is correct
10 Correct 228 ms 19432 KB Output is correct
11 Correct 130 ms 10576 KB Output is correct
12 Correct 75 ms 9580 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 18704 KB Output is correct
2 Correct 456 ms 18636 KB Output is correct
3 Correct 457 ms 18656 KB Output is correct
4 Correct 175 ms 12472 KB Output is correct
5 Correct 272 ms 19216 KB Output is correct
6 Correct 104 ms 9920 KB Output is correct
7 Correct 335 ms 18416 KB Output is correct
8 Correct 365 ms 18636 KB Output is correct
9 Correct 333 ms 18316 KB Output is correct
10 Correct 228 ms 19432 KB Output is correct
11 Correct 130 ms 10576 KB Output is correct
12 Correct 75 ms 9580 KB Output is correct
13 Correct 492 ms 19060 KB Output is correct
14 Correct 494 ms 19012 KB Output is correct
15 Correct 451 ms 18628 KB Output is correct
16 Correct 225 ms 12796 KB Output is correct
17 Correct 295 ms 19608 KB Output is correct
18 Correct 101 ms 9932 KB Output is correct
19 Correct 457 ms 19068 KB Output is correct
20 Correct 537 ms 19060 KB Output is correct
21 Correct 431 ms 19016 KB Output is correct
22 Correct 218 ms 19576 KB Output is correct
23 Correct 117 ms 10480 KB Output is correct
24 Correct 72 ms 9624 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 13 ms 3316 KB Output is correct
8 Correct 11 ms 3424 KB Output is correct
9 Correct 13 ms 3416 KB Output is correct
10 Correct 7 ms 3156 KB Output is correct
11 Correct 10 ms 3404 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 10 ms 3336 KB Output is correct
14 Correct 10 ms 3384 KB Output is correct
15 Correct 10 ms 3368 KB Output is correct
16 Correct 7 ms 3464 KB Output is correct
17 Correct 8 ms 3164 KB Output is correct
18 Correct 4 ms 3028 KB Output is correct
19 Correct 440 ms 18704 KB Output is correct
20 Correct 456 ms 18636 KB Output is correct
21 Correct 457 ms 18656 KB Output is correct
22 Correct 175 ms 12472 KB Output is correct
23 Correct 272 ms 19216 KB Output is correct
24 Correct 104 ms 9920 KB Output is correct
25 Correct 335 ms 18416 KB Output is correct
26 Correct 365 ms 18636 KB Output is correct
27 Correct 333 ms 18316 KB Output is correct
28 Correct 228 ms 19432 KB Output is correct
29 Correct 130 ms 10576 KB Output is correct
30 Correct 75 ms 9580 KB Output is correct
31 Correct 492 ms 19060 KB Output is correct
32 Correct 494 ms 19012 KB Output is correct
33 Correct 451 ms 18628 KB Output is correct
34 Correct 225 ms 12796 KB Output is correct
35 Correct 295 ms 19608 KB Output is correct
36 Correct 101 ms 9932 KB Output is correct
37 Correct 457 ms 19068 KB Output is correct
38 Correct 537 ms 19060 KB Output is correct
39 Correct 431 ms 19016 KB Output is correct
40 Correct 218 ms 19576 KB Output is correct
41 Correct 117 ms 10480 KB Output is correct
42 Correct 72 ms 9624 KB Output is correct
43 Correct 585 ms 21112 KB Output is correct
44 Correct 503 ms 21108 KB Output is correct
45 Correct 532 ms 21060 KB Output is correct
46 Correct 192 ms 14392 KB Output is correct
47 Correct 317 ms 25048 KB Output is correct
48 Correct 104 ms 9728 KB Output is correct
49 Correct 470 ms 20652 KB Output is correct
50 Correct 469 ms 21004 KB Output is correct
51 Correct 445 ms 20484 KB Output is correct
52 Correct 264 ms 26164 KB Output is correct
53 Correct 140 ms 11984 KB Output is correct