oj.uz

Submission #531731

# Submission time Handle Problem Language Result Execution time Memory
531731 2022-03-01T10:52:37 Z akhan42 Examination (JOI19_examination) C++17
41 / 100
 2359 ms 16760 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define at(m, k) (m.find(k) != m.end() ? m[k] : 0)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 100 * 1000 + 10;
int n, q;
int a[MX], b[MX], c[MX];
vi a2i[MX], b2i[MX];
int cl[MX];
int S = 350;


struct Fenw {
	static const int mx = 2 * MX - 1;
	vi bit;

	Fenw() {
		bit.assign(2 * MX, 0);
	}

	void upd(int i, int v) {
		for(i += 1; i <= mx; i += i & (-i))
			bit[i] += v;
	}

	int psum(int i) {
		int sum = 0;
		for(; i > 0; i -= i & (-i))
			sum += bit[i];
		return sum;
	}

	int query(int cc) {
		return psum(mx) - psum(cc);
	}
};



bool cmp(pair<ii, ii> p1, pair<ii, ii> p2) {
	ii a = p1.F, b = p2.F;

	if(cl[a.F] != cl[b.F])
		return a.F < b.F;
	return (cl[a.F] % 2) ? a.S > b.S : a.S < b.S;
}


struct Mo {
	int l, r;
	Fenw fenw;

	void init(int l, int r) {
		this->l = l, this->r = r;

		forn(i, n)
			if(a[i] >= l && b[i] >= r)
				fenw.upd(c[i], 1);
	}

	void add_left() {
		l -= 1;
		for(int i: a2i[l])
			if(b[i] >= r)
				fenw.upd(c[i], 1);
	}

	void pop_left() {
		for(int i: a2i[l])
			if(b[i] >= r)
				fenw.upd(c[i], -1);
		l += 1;
	}

	void add_right() {
		for(int i: b2i[r])
			if(a[i] >= l)
				fenw.upd(c[i], -1);
		r += 1;
	}

	void pop_right() {
		r -= 1;
		for(int i: b2i[r])
			if(a[i] >= l)
				fenw.upd(c[i], 1);
	}

	int get_ans(int cc) {
		return fenw.query(cc);
	}
};


void solve()
{
	cin >> n >> q;
	forn(i, n)
	{
		cin >> a[i] >> b[i];
		c[i] = a[i] + b[i];

		a2i[a[i]].pb(i);
		b2i[b[i]].pb(i);
	}

	int ct = 0, i = 0;
	forn(l, MX) {
		if(ct != 0 && ct + sz(a2i[l]) > S) {
			ct = sz(a2i[l]);
			i += 1;
		} else {
			ct += sz(a2i[l]);
		}
		cl[l] = i;
	}

	vector<pair<ii, ii>> qs;

	forn(ind, q) {
		int l, r, cc;
		cin >> l >> r >> cc;

		qs.pb({{l, r}, {cc, ind}});
	}

	sort(all(qs), cmp);

	Mo mo;
	vi ans(q);

	forn(i, q) {
		int l = qs[i].F.F, r = qs[i].F.S, cc = qs[i].S.F, ind = qs[i].S.S;

		if(i == 0) {
			mo.init(l, r);
		}
		else {
			while(l != mo.l || r != mo.r) {
				if(l < mo.l)
					mo.add_left();
				else if(r > mo.r)
					mo.add_right();
				else if(l > mo.l)
					mo.pop_left();
				else
					mo.pop_right();
			}
		}

		ans[ind] = mo.get_ans(cc);
//		cout << l << ' ' << r << ' ' << ans[ind] << '\n';
	}

	for(int el: ans)
		cout << el << '\n';
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("haybales.in", "r", stdin);
//	freopen("haybales.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--)
		solve();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6152 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6172 KB Output is correct
4 Runtime error 8 ms 10060 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2358 ms 16280 KB Output is correct
2 Correct 2359 ms 16296 KB Output is correct
3 Correct 1971 ms 16284 KB Output is correct
4 Correct 813 ms 14152 KB Output is correct
5 Correct 156 ms 14160 KB Output is correct
6 Correct 78 ms 12136 KB Output is correct
7 Correct 588 ms 16196 KB Output is correct
8 Correct 669 ms 16380 KB Output is correct
9 Correct 567 ms 16104 KB Output is correct
10 Correct 81 ms 13788 KB Output is correct
11 Correct 759 ms 13832 KB Output is correct
12 Correct 53 ms 11316 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2358 ms 16280 KB Output is correct
2 Correct 2359 ms 16296 KB Output is correct
3 Correct 1971 ms 16284 KB Output is correct
4 Correct 813 ms 14152 KB Output is correct
5 Correct 156 ms 14160 KB Output is correct
6 Correct 78 ms 12136 KB Output is correct
7 Correct 588 ms 16196 KB Output is correct
8 Correct 669 ms 16380 KB Output is correct
9 Correct 567 ms 16104 KB Output is correct
10 Correct 81 ms 13788 KB Output is correct
11 Correct 759 ms 13832 KB Output is correct
12 Correct 53 ms 11316 KB Output is correct
13 Correct 2176 ms 16732 KB Output is correct
14 Correct 1844 ms 16676 KB Output is correct
15 Correct 1961 ms 16300 KB Output is correct
16 Correct 816 ms 14476 KB Output is correct
17 Correct 134 ms 14484 KB Output is correct
18 Correct 90 ms 12244 KB Output is correct
19 Correct 1982 ms 16760 KB Output is correct
20 Correct 1943 ms 16716 KB Output is correct
21 Correct 930 ms 16716 KB Output is correct
22 Correct 102 ms 13768 KB Output is correct
23 Correct 788 ms 13816 KB Output is correct
24 Correct 57 ms 11276 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6152 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6172 KB Output is correct
4 Runtime error 8 ms 10060 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -