Submission #497379

#	Time	Username	Problem	Language	Result	Execution time	Memory
497379		maomao90	New Home (APIO18_new_home)	C++17	0 / 100	395 ms	34248 KiB

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 y < o.y;
	}
};

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
5 3
5 6
5 9
1 10
*/

Compilation message (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20