Submission #106961

#	Time	Username	Problem	Language	Result	Execution time	Memory
106961		polyfish	New Home (APIO18_new_home)	C++14	57 / 100	5071 ms	244444 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 {
 
    int n;
    vector<int> st;
 
    void init(int _n) {
        n = _n;
        st.resize(4*n);
    }
 
    void upd(int pos, int val, int l, int r, int idx) {
        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, int r, int idx) {
        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);
    }
 
    void upd(int pos, int val) {
        upd(pos, val, 1, n, 1);
    }
 
    bool get(int u, int v, int val) {
        return get(u, v, val, 1, n, 1);
    }
 
};
 
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;
 
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() {
    tr.init(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);
 
    tr.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);
 
        tr.upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        tr.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);
 
        tr.upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        tr.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 = 2e8;
 
	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (tr.get(1, get_id(x-mid-1), get_id(x+mid)))
			r = mid;
		else
			l = mid;
	}
 
	for (int i=l; i<=r; ++i) {
		if (tr.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:162: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:236:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQueries; ++i)
     ^~~
new_home.cpp:239: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