Submission #361334

#	Time	Username	Problem	Language	Result	Execution time	Memory
361334		AmShZ	New Home (APIO18_new_home)	C++11	12 / 100	5098 ms	32500 KiB

new_home

//khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;

int n, k, q, ans[xn], cnt[xn], ptr, ted;
int nxt[xn];
ppp a[xn];
pii b[xn];
vector <pip> query;
set <pii> st[xn];

void remove(int x){
	-- cnt[x];
	if (!cnt[x])
		-- ted;
}
void add(int x){
	if (!cnt[x])
		++ ted;
	++ cnt[x];
}

void solve(){
	sort(a + 1, a + n + 1);
	a[n + 1].A.A = inf;
	for (int i = 1; i <= n; ++ i){
		if (i)
			remove(a[i - 1].A.B);
		while (ptr <= n && ted < k)
			++ ptr, add(a[ptr].A.B);
		nxt[i] = ptr;
	}
	nxt[0] = nxt[n + 1] = n + 1;
	while (q --){
		int x, y, ans = inf;
		cin >> x >> y;
		int l = 0, r = n + 1, mid;
		while (r - l > 1){
			mid = (l + r) / 2;
			if (x - a[mid].A.A < a[nxt[mid]].A.A - x)
				r = mid;
			else
				l = mid;
		}
		ans = min(ans, max(x - a[l].A.A, a[nxt[l]].A.A - x));
		ans = min(ans, max(x - a[r].A.A, a[nxt[l]].A.A - x));
		if (x > 1e8)
			ans = - 1;
		cout << ans << endl;
	}
}

int main(){
	InTheNameOfGod;
	
	cin >> n >> k >> q;
	for (int i = 1; i <= n; ++ i){
		int x, t, l, r;
		cin >> x >> t >> l >> r;
		a[i] = {{x, t}, {l, r}};
		query.push_back({l, {0, i}});
		query.push_back({r, {2, i}});
	}
	if (n > 6e4){
		solve();
		return 0;
	}
	for (int i = 1; i <= q; ++ i){
		int x, y;
		cin >> x >> y;
		b[i] = {x, y};
		query.push_back({y, {1, i}});
	}
	for (int i = 1; i <= k; ++ i)
		st[i].insert({inf, 0}), st[i].insert({- inf, 0});
	sort(all(query));
	for (pip Q : query){
		int id = Q.B.B, t = Q.B.A;
		if (t == 0)
			st[a[id].A.B].insert({a[id].A.A, id});
		else if (t == 2)
			st[a[id].A.B].erase({a[id].A.A, id});
		else{
			int mx = 0;
			for (int i = 1; i <= k; ++ i){
				pii x = *st[i].lower_bound({b[id].A, 0});
				pii y = *prev(st[i].lower_bound({b[id].A, 0}));
				mx = max(mx, min(x.A - b[id].A, b[id].A - y.A));
			}
			if (mx > 1e8)
				ans[id] = - 1;
			else
				ans[id] = mx;
		}
	}
	for (int i = 1; i <= q; ++ i)
		cout << ans[i] << endl;
			
	return 0;
}

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