Submission #497382

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
497382	2021-12-23T04:10:26 Z	maomao90	New Home (APIO18_new_home)	C++17	10 / 100	442 ms	56080 KB

new_home

// When they saw the star, they were overjoyed. On coming to the house,
// they saw the child with his mother Mary, and they bowed down and
// worhipped him. Then they opened their treasures and presented him with 
// gifts of gold, frankincense and myrrh.
// Matthew 2:10-11
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005

struct store {
	int x, t, a, b;
	bool operator< (const store& o) const {
		return x < o.x;
	}
};
struct qry {
	int l, y, id;
	bool operator< (const qry& o) const {
		return l < o.l;
	}
};

int n, k, q;
store stores[MAXN];
vector<store> grp[MAXN];
qry qrys[MAXN];
vii dis;
set<ii> st;
int ans[MAXN];

void insert(int x, int y) {
	debug(" -> %d %d\n", x, y);
	if (st.empty()) {
		st.insert(MP(x, y));
		return;
	}
	auto it = prev(st.upper_bound(MP(x, INF)));
	if (it -> SE >= y) {
		return;
	}
	if (it -> FI == x) {
		st.erase(it);
	}
	it = next(st.insert(MP(x, y)).FI);
	while (it != st.end() && it -> SE <= y) {
		it = st.erase(it);
	}
	return;
}

int main() {
	int _t = 1;
   	//scanf("%d", &_t);
	while (_t--) {
		scanf("%d%d%d", &n, &k, &q);
		REP (i, 0, n) {
			int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
			x *= 2;
			stores[i] = (store) {x, t, a, b};
			dis.pb(MP(a, i));
			dis.pb(MP(b, i + n));
		}
		REP (i, 0, q) {
			int l, y; scanf("%d%d", &l, &y);
			l *= 2;
			qrys[i] = (qry) {l, y, i};
			dis.pb(MP(y, i + 2 * n));
		}
		sort(ALL(dis));
		int prv = -1, sze = 0;
		for (auto [a, b] : dis) {
			if (a != prv) {
				sze++;
				prv = a;
			}
			if (b < n) {
				stores[b].a = sze - 1;
			} else if (b < 2 * n) {
				stores[b - n].b = sze - 1;
			} else {
				qrys[b - 2 * n].y = sze - 1;
			}
		}
		sort(stores, stores + n);
		sort(qrys, qrys + q);
		REP (i, 0, n) {
			grp[stores[i].t].pb(stores[i]);
		}
		REP (i, 1, k + 1) {
			assert(!grp[i].empty());
			insert(-INF, grp[i][0].x);
			REP (j, 0, grp[i].size()) {
				insert(grp[i][j].x, 
						j + 1 == grp[i].size() ? INF : grp[i][j + 1].x);
			}
		}
		for (auto [a, b] : st) {
			debug("%d %d\n", a, b);
		}
		auto it = st.begin();
		REP (i, 0, q) {
			while (next(it) != st.end() && 
					(it -> SE + next(it) -> FI) / 2 < qrys[i].l) {
				it = next(it);
			}
			ans[qrys[i].id] = min(it -> SE - qrys[i].l, qrys[i].l - it -> FI);
		}
		REP (i, 0, q) {
			printf("%d\n", ans[i] / 2);
		}
	}
	return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
7 3
5 6
5 9
1 10
*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<store>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  124 |    REP (j, 0, grp[i].size()) {
      |         ~~~~~~~~~~~~~~~~~~~             
new_home.cpp:124:4: note: in expansion of macro 'REP'
  124 |    REP (j, 0, grp[i].size()) {
      |    ^~~
new_home.cpp:126:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<store>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       j + 1 == grp[i].size() ? INF : grp[i][j + 1].x);
      |       ~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:129:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  129 |   for (auto [a, b] : st) {
      |             ^~~~~~
new_home.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d%d", &n, &k, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:89:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |    int l, y; scanf("%d%d", &l, &y);
      |              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Incorrect	4 ms	7244 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Incorrect	4 ms	7244 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	34352 KB	Output is correct
2	Correct	338 ms	44128 KB	Output is correct
3	Correct	387 ms	49676 KB	Output is correct
4	Correct	358 ms	48016 KB	Output is correct
5	Correct	442 ms	56080 KB	Output is correct
6	Correct	359 ms	45416 KB	Output is correct
7	Correct	372 ms	49748 KB	Output is correct
8	Correct	351 ms	47540 KB	Output is correct
9	Correct	327 ms	47344 KB	Output is correct
10	Correct	323 ms	45940 KB	Output is correct
11	Correct	293 ms	43688 KB	Output is correct
12	Correct	306 ms	45452 KB	Output is correct