oj.uz

Submission #1080051

# Submission time Handle Problem Language Result Execution time Memory
1080051 2024-08-29T06:36:57 Z BuzzyBeez Examination (JOI19_examination) C++17
0 / 100
 333 ms 9840 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

vector<int> tbc;

void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(int key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}

struct point {
	int Ox, Oy, Oz; char op; int id;
	
	point() {}
	
	friend istream& operator >> (istream& in, point& o) {
		in >> o.Ox >> o.Oy >> o.Oz;
		tbc.push_back(o.Oz); o.op = '?';
		return in;
	}
	
	friend ostream& operator << (ostream& out, const point& o) {
		out << o.op << ' ' << o.Ox << ' ' << o.Oy << ' ' << o.Oz;
		return out;
	}
} S[N + 8];
int ans[100008];

bool by_Ox(point& a, point& b) {return a.Ox > b.Ox;}
bool by_Oy(point& a, point& b) {return a.Oy > b.Oy;}

struct Binary_Indexed_Tree {
	int BIT[N + 8];
	
	Binary_Indexed_Tree() {memset(BIT, 0, sizeof BIT);}
	
	int pt, res;
	
	void update(int u, int v) {
	    pt = u;
	    while (pt <= N) {
	    	BIT[pt] += v;
	        pt += pt & -pt;
	    }
	}
	
	int pf(int p) {
		if (p <= 0) return 0;
	    pt = p; res = 0;
	    while (pt) {
	        res += BIT[pt];
	        pt -= pt & -pt;
	    }
	    return res;
	}
	
	int range(int l, int r) {
		if (l > r) return 0;
		return pf(r) - pf(l - 1);
	}
	
	int query(int i) {return range(i, N);}
} tree;

void dnc(int l, int r) {
	if (l >= r) return;
	int mid = (l + r) / 2, pt1, pt2 = l - 1;
	dnc(l, mid); dnc(mid + 1, r);
	vector<int> del;
	for (pt1 = mid + 1; pt1 <= r; ++pt1) if (S[pt1].op == '?') {
		while (pt2 < mid && S[pt2 + 1].Oy >= S[pt1].Oy) {
			++pt2;
			if (S[pt2].op == '+') tree.update(S[pt2].Oz, +1), del.push_back(S[pt2].Oz);
		}
		ans[S[pt1].id] += tree.query(S[pt1].Oz);
	}
	for (int i : del) tree.update(i, -1);
	del.clear();
	sort(S + l, S + r + 1, by_Oy);
	// cout << l << ' ' << r << '\n';
	// for (int i = l; i <= r; ++i) cout << S[i] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> S[i].Ox >> S[i].Oy; S[i].Oz = S[i].Ox + S[i].Oy;
		S[i].op = '+'; tbc.push_back(S[i].Oz);
	}
	for (int i = 1; i <= q; ++i) cin >> S[n + i], S[n + i].id = i;
	compress(); sort(S + 1, S + n + q + 1, by_Ox);
	for (int i = 1; i <= n + q; ++i) S[i].Oz = order(S[i].Oz);
	dnc(1, n + q);
	for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 7 ms 2892 KB Output is correct
10 Correct 6 ms 2652 KB Output is correct
11 Incorrect 6 ms 2856 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 9840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 9840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 7 ms 2892 KB Output is correct
10 Correct 6 ms 2652 KB Output is correct
11 Incorrect 6 ms 2856 KB Output isn't correct
12 Halted 0 ms 0 KB -