Submission #106974

#	Time	Username	Problem	Language	Result	Execution time	Memory
106974		polyfish	New Home (APIO18_new_home)	C++11	57 / 100	5109 ms	230608 KiB

new_home

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "new_home"

const int MAX_N = 300002;
const int INF = 1e9+100;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct segment_tree {



};

struct store {
	int x, t, a, b;
};

struct query {
	int l, y;
};

int n, k, nQueries, res[MAX_N];
vector<int> T, L, store_event[MAX_N*3], q[MAX_N*3];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*3];
multiset<int> g[MAX_N*2];
segment_tree tr;
vector<int> st;

void upd(int pos, int val, int l=1, int r=L.size(), int idx=1) {
    if (pos<l || pos>r)
        return;

    if (l==r) {
        st[idx] = val;
        return;
    }

    int mid = (l + r) / 2;
    upd(pos, val, l, mid, idx*2);
    upd(pos, val, mid+1, r, idx*2+1);

    st[idx] = max(st[idx*2], st[idx*2+1]);
}

bool get(int u, int v, int val, int l=1, int r=L.size(), int idx=1) {
    if (v<l || u>r || st[idx]<=val)
        return true;

    if (u<=l && r<=v)
        return st[idx]<=val;

    int mid = (l + r) / 2;
    return get(u, v, val, mid+1, r, idx*2+1) && get(u, v, val, l, mid, idx*2);
}

int read_int() {
    char c;

    for (c = getchar(); c<'0' || c>'9'; c = getchar());

    int res = c - '0';

    for (c = getchar(); '0'<=c && c<='9'; c = getchar())
        res = res * 10 + c - '0';

    return res;
}

void read_input() {
	n = read_int();
	k = read_int();
	nQueries = read_int();

	for (int i=1; i<=n; ++i) {
        s[i].x = read_int();
        s[i].t = read_int();
        s[i].a = read_int();
        s[i].b = read_int();
	}

	for (int i=1; i<=nQueries; ++i) {
		Q[i].l = read_int();
		Q[i].y = read_int();
	}
}

void compress() {
    L.push_back(-INF);
    L.push_back(INF);

	for (int i=1; i<=n; ++i) {
		T.push_back(s[i].a);
		T.push_back(s[i].b+1);
		L.push_back(s[i].x);
	}

	for (int i=1; i<=nQueries; ++i) {
		T.push_back(Q[i].y);
	}

	#define uniq(P) {sort(P.begin(), P.end()); P.resize(unique(P.begin(), P.end()) - P.begin());}
    uniq(T);
    uniq(L);
	#undef uniq

	#define get_pos(P, x) lower_bound(P.begin(), P.end(), x) - P.begin() + 1
	for (int i=1; i<=n; ++i) {
		s[i].a = get_pos(T, s[i].a);
		s[i].b = get_pos(T, s[i].b+1);
		s[i].x = get_pos(L, s[i].x);
	}

	for (int i=1; i<=nQueries; ++i) {
		Q[i].y = get_pos(T, Q[i].y);
//		Q[i].l = get_pos(L, Q[i].l);
	}
	#undef uniq
}

void init() {
    st.resize(4*L.size());

	for (int i=1; i<=n; ++i) {
		store_event[s[i].a].push_back(i);
		store_event[s[i].b].push_back(-i);
	}

	for (int i=1; i<=nQueries; ++i) {
		q[Q[i].y].push_back(i);
	}

	for (int i=1; i<=k; ++i) {
		++pos[i][1];
		++pos[i][L.size()];
        g[1].insert(L.size());
	}

	for (int i=1; i<=L.size(); ++i)
        g[i].insert(0);

    upd(1, L.size());
}

void add_store(int idx) {
	int tmp = ++pos[s[idx].t][s[idx].x];

	if (tmp==1) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

        g[u->first].erase(g[u->first].find(v->first));
        g[u->first].insert(s[idx].x);
        g[s[idx].x].insert(v->first);

        upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        upd(s[idx].x, *g[s[idx].x].rbegin());
//        cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';
	}
}

void remove_store(int idx) {
	int tmp = --pos[s[idx].t][s[idx].x];

	if (!tmp) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

        g[u->first].erase(g[u->first].find(s[idx].x));
        g[s[idx].x].erase(g[s[idx].x].find(v->first));
        g[u->first].insert(v->first);

        upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        upd(s[idx].x, *g[s[idx].x].rbegin());
//        cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';

        pos[s[idx].t].erase(s[idx].x);
	}
}

int get_id(int x) {
    return upper_bound(L.begin(), L.end(), x) - L.begin();
}

int bisect(int x) {
	int l = 0, r = 1e8;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (get(1, get_id(x-mid-1), get_id(x+mid)))
			r = mid;
		else
			l = mid;
	}

	for (int i=l; i<=r; ++i) {
		if (get(1, get_id(x-i-1), get_id(x+i)))
			return i;
	}

	return -1;
}

void solve() {
    int tmp = 0;
    for (int i=1; i<=nQueries; ++i)
        tmp = max(tmp, Q[i].y);

	for (int i=1; i<=tmp; ++i) {
		for (auto x : store_event[i]) {
			if (x>0)
				add_store(x);
			else
				remove_store(-x);
		}

//		debug(tr.get(1, 2, 4));
		for (auto x : q[i])
			res[x] = bisect(Q[x].l);
	}

//	debug(tr.get())
	for (int i=1; i<=nQueries; ++i)
		cout << res[i] << '\n';
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	compress();
	init();
	solve();
}

Compilation message (stderr)

new_home.cpp: In function 'void init()':
new_home.cpp:149:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=L.size(); ++i)
                ~^~~~~~~~~~
new_home.cpp: In function 'void solve()':
new_home.cpp:223:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQueries; ++i)
     ^~~
new_home.cpp:226:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=1; i<=tmp; ++i) {
  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20