oj.uz

Submission #289148

# Submission time Handle Problem Language Result Execution time Memory
289148 2020-09-02T12:11:07 Z tonowak Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 6904 KB 
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

using P = pair<int, int>;
LL operator*(P a, P b) {
	return a.first * LL(b.second) - a.second * LL(b.first);
}
P operator-(P a, P b) {
	return {a.first - b.first, a.second - b.second};
}
int sign(LL x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}
LL dir(P a, P b, P c) {
	return (b - a) * (c - b);
}

P human1, human2;

bool intersects(P a, P b) {
	// debug(a, b);
	if(sign(dir(a, human1, b)) == sign(dir(a, human2, b)))
		return false;
	LL h1ah2 = dir(human1, a, human2),
	   h1bh2 = dir(human1, b, human2);
	// debug(h1ah2, h1bh2);
	if(sign(h1ah2) == sign(h1bh2)) {
		if(abs(h1ah2) < abs(h1bh2))
			return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	vector<vector<P>> points(m);
	REP(i, n) {
		int x, y, c;
		cin >> x >> y >> c;
		points[--c].emplace_back(x, y);
	}
	cin >> human1.first >> human1.second >> human2.first >> human2.second;
	debug(points);
	debug(human1, human2);

	map<pair<int, int>, int> answers;
	int q;
	cin >> q;
	while(q --> 0) {
		int f, g;
		cin >> f >> g;
		--f, --g;
		if(answers.find(make_pair(f, g)) != answers.end()) {
			cout << answers[make_pair(f, g)] << '\n';
			continue;
		}

		int ret = 0;
		for(P p1 : points[f])
			for(P p2 : points[g]) {
				bool got = intersects(p1, p2);
				debug(p1, p2, got);
				ret += got;
			}
		cout << (answers[make_pair(f, g)] = ret) << '\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 384 KB Output is correct
2 Correct 59 ms 384 KB Output is correct
3 Correct 79 ms 760 KB Output is correct
4 Correct 122 ms 6904 KB Output is correct
5 Correct 117 ms 6904 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 21 ms 384 KB Output is correct
9 Correct 20 ms 384 KB Output is correct
10 Correct 21 ms 384 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3421 ms 888 KB Output is correct
2 Execution timed out 4080 ms 640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 384 KB Output is correct
2 Correct 59 ms 384 KB Output is correct
3 Correct 79 ms 760 KB Output is correct
4 Correct 122 ms 6904 KB Output is correct
5 Correct 117 ms 6904 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 21 ms 384 KB Output is correct
9 Correct 20 ms 384 KB Output is correct
10 Correct 21 ms 384 KB Output is correct
11 Correct 3421 ms 888 KB Output is correct
12 Execution timed out 4080 ms 640 KB Time limit exceeded
13 Halted 0 ms 0 KB -