oj.uz

Submission #590701

# Submission time Handle Problem Language Result Execution time Memory
590701 2022-07-06T08:53:46 Z Bungmint Examination (JOI19_examination) C++17
20 / 100
 485 ms 18668 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);
	for (int i : rep(n)) {
		int s, t;
		cin >> s >> t;
		t++;
		sorted_by_sum[i] = {s, t};
		xs[i] = s;
		// 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;
		y++;
		xs.pb(x);
	}
	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());
	for (auto &[s, t] : sorted_by_sum) {
		s = lb(all(xs), s) - xs.begin() + 1;
		bit.upd(s, t, 1);
	}
	bit.init();
	int ptr{};
	for (int i : rep(q)) {
		auto& [x, y, z] = queries[ind[i]];
		x = lb(all(xs), x) - xs.begin() + 1;
		while (ptr < n && xs[sorted_by_sum[ptr].fi - 1] + sorted_by_sum[ptr].se >= z) {
			auto [s, t] = sorted_by_sum[ptr++];
			bit.upd(s, t, 1);
		}
		ans[ind[i]] = bit.query(x, sz(xs), y, INF + 1);
	}
	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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2820 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2768 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 10 ms 3412 KB Output is correct
8 Correct 10 ms 3412 KB Output is correct
9 Correct 10 ms 3284 KB Output is correct
10 Correct 6 ms 3028 KB Output is correct
11 Correct 7 ms 3412 KB Output is correct
12 Incorrect 5 ms 2912 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 17876 KB Output is correct
2 Correct 402 ms 17972 KB Output is correct
3 Correct 387 ms 17796 KB Output is correct
4 Correct 151 ms 11656 KB Output is correct
5 Correct 247 ms 18544 KB Output is correct
6 Correct 94 ms 9092 KB Output is correct
7 Correct 312 ms 17644 KB Output is correct
8 Correct 333 ms 17704 KB Output is correct
9 Correct 296 ms 17504 KB Output is correct
10 Correct 200 ms 18668 KB Output is correct
11 Correct 122 ms 9804 KB Output is correct
12 Correct 68 ms 8708 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 17876 KB Output is correct
2 Correct 402 ms 17972 KB Output is correct
3 Correct 387 ms 17796 KB Output is correct
4 Correct 151 ms 11656 KB Output is correct
5 Correct 247 ms 18544 KB Output is correct
6 Correct 94 ms 9092 KB Output is correct
7 Correct 312 ms 17644 KB Output is correct
8 Correct 333 ms 17704 KB Output is correct
9 Correct 296 ms 17504 KB Output is correct
10 Correct 200 ms 18668 KB Output is correct
11 Correct 122 ms 9804 KB Output is correct
12 Correct 68 ms 8708 KB Output is correct
13 Incorrect 485 ms 18288 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2820 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2768 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 10 ms 3412 KB Output is correct
8 Correct 10 ms 3412 KB Output is correct
9 Correct 10 ms 3284 KB Output is correct
10 Correct 6 ms 3028 KB Output is correct
11 Correct 7 ms 3412 KB Output is correct
12 Incorrect 5 ms 2912 KB Output isn't correct
13 Halted 0 ms 0 KB -