oj.uz

Submission #531746

# Submission time Handle Problem Language Result Execution time Memory
531746 2022-03-01T11:23:24 Z akhan42 Examination (JOI19_examination) C++17
22 / 100
 1908 ms 27004 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 = 300;


struct Fenw {
	int mx = MX - 1;
	vi bit;

	Fenw() {
		bit.assign(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);
			else
				break;
	}

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

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

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

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


void comp(vi& v) {
	set<int> sl;
	for(int el: v)
		sl.insert(el);

	int ct = 0;
	map<int, int> v2i;
	for(int el: sl)
		v2i[el] = ct++;

	for(int& el: v)
		el = v2i[el];
}


bool cmp1(int i, int j) {
	return b[i] > b[j];
}


bool cmp2(int i, int j) {
	return a[i] > a[j];
}


void solve()
{
	cin >> n >> q;

	vi as, bs, cs;
	set<int> sas, sbs;
	int mx_x = -1, mx_y = -1;
	forn(i, n) {
		int x, y;
		cin >> x >> y;

		as.pb(x);
		bs.pb(y);
		cs.pb(x + y);

		sas.insert(x);
		sbs.insert(y);

		maxeq(mx_x, x);
		maxeq(mx_y, y);
	}

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

		if(sas.lower_bound(l) != sas.end())
			l = *sas.lower_bound(l);
		else
			l = mx_x + 1;

		if(sbs.lower_bound(r) != sbs.end())
			r = *sbs.lower_bound(r);
		else
			r = mx_y + 1;

		as.pb(l);
		bs.pb(r);
		cs.pb(cc);
	}

	comp(as);
	comp(bs);
	comp(cs);

	forn(i, n)
	{
		a[i] = as[i];
		b[i] = bs[i];
		c[i] = cs[i];

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

	forn(i, MX) {
		sort(all(a2i[i]), cmp1);
		sort(all(b2i[i]), cmp2);
	}

	int ct = 0, i = 0;
	forn(l, MX) {
		if(sz(a2i[l]) > S || ct > 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 = as[ind + n], r = bs[ind + n], cc = cs[ind + n];

		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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 20 ms 6812 KB Output is correct
8 Correct 19 ms 6816 KB Output is correct
9 Correct 20 ms 6860 KB Output is correct
10 Correct 18 ms 6700 KB Output is correct
11 Correct 16 ms 6604 KB Output is correct
12 Correct 11 ms 6092 KB Output is correct
13 Correct 19 ms 6604 KB Output is correct
14 Correct 20 ms 6572 KB Output is correct
15 Correct 18 ms 6604 KB Output is correct
16 Correct 9 ms 6348 KB Output is correct
17 Correct 16 ms 6616 KB Output is correct
18 Correct 5 ms 6092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1889 ms 23992 KB Output is correct
2 Correct 1908 ms 23920 KB Output is correct
3 Correct 1888 ms 23944 KB Output is correct
4 Correct 964 ms 20004 KB Output is correct
5 Correct 349 ms 19996 KB Output is correct
6 Correct 107 ms 13192 KB Output is correct
7 Correct 855 ms 23936 KB Output is correct
8 Correct 913 ms 23968 KB Output is correct
9 Correct 761 ms 23968 KB Output is correct
10 Correct 294 ms 19748 KB Output is correct
11 Correct 923 ms 19748 KB Output is correct
12 Correct 71 ms 13148 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1889 ms 23992 KB Output is correct
2 Correct 1908 ms 23920 KB Output is correct
3 Correct 1888 ms 23944 KB Output is correct
4 Correct 964 ms 20004 KB Output is correct
5 Correct 349 ms 19996 KB Output is correct
6 Correct 107 ms 13192 KB Output is correct
7 Correct 855 ms 23936 KB Output is correct
8 Correct 913 ms 23968 KB Output is correct
9 Correct 761 ms 23968 KB Output is correct
10 Correct 294 ms 19748 KB Output is correct
11 Correct 923 ms 19748 KB Output is correct
12 Correct 71 ms 13148 KB Output is correct
13 Incorrect 1858 ms 27004 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 20 ms 6812 KB Output is correct
8 Correct 19 ms 6816 KB Output is correct
9 Correct 20 ms 6860 KB Output is correct
10 Correct 18 ms 6700 KB Output is correct
11 Correct 16 ms 6604 KB Output is correct
12 Correct 11 ms 6092 KB Output is correct
13 Correct 19 ms 6604 KB Output is correct
14 Correct 20 ms 6572 KB Output is correct
15 Correct 18 ms 6604 KB Output is correct
16 Correct 9 ms 6348 KB Output is correct
17 Correct 16 ms 6616 KB Output is correct
18 Correct 5 ms 6092 KB Output is correct
19 Correct 1889 ms 23992 KB Output is correct
20 Correct 1908 ms 23920 KB Output is correct
21 Correct 1888 ms 23944 KB Output is correct
22 Correct 964 ms 20004 KB Output is correct
23 Correct 349 ms 19996 KB Output is correct
24 Correct 107 ms 13192 KB Output is correct
25 Correct 855 ms 23936 KB Output is correct
26 Correct 913 ms 23968 KB Output is correct
27 Correct 761 ms 23968 KB Output is correct
28 Correct 294 ms 19748 KB Output is correct
29 Correct 923 ms 19748 KB Output is correct
30 Correct 71 ms 13148 KB Output is correct
31 Incorrect 1858 ms 27004 KB Output isn't correct
32 Halted 0 ms 0 KB -