Submission #108377

#	Time	Username	Problem	Language	Result	Execution time	Memory
108377		RezwanArefin01	New Home (APIO18_new_home)	C++17	0 / 100	4739 ms	76512 KiB

new_home

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 3e5 + 5; 
const int inf = 1e9 + 7;
int n, k, q, ans[N], t[8*N], M;
vector<int> v = {0}, tree; 
multiset<int> pos[N], Q; 

struct event {
	int x, y, t, id; 
	event(int x = 0, int y = 0, int t = 0, int id = 0) : 
		x(x), y(y), t(t), id(id) {}
	bool operator < (const event &e) const {
		return y == e.y ? id < e.id : y < e.y; 
	}
};

vector<event> E; 

void update(int node, int l, int r, int i, int x) {
	if(l == r) return void(t[node] = x);
	int m = l + r >> 1; 
	if(i <= m) update(node << 1, l, m, i, x); 
	else update(node << 1 | 1, m + 1, r, i, x); 
	t[node] = max(t[node << 1], t[node << 1 | 1]); 
}

int query(int node, int l, int r, int i, int j) {
	if(r < i || l > j) return 0; 
	if(i <= l && r <= j) return t[node];
	int m = l + r >> 1; 
	return max(query(node << 1, l, m, i, j), 
			query(node << 1 | 1, m + 1, r, i, j)); 
}
void addPoint(int x, int t) {
	int idx = lower_bound(v.begin(), v.end(), x) - v.begin();	
		
	auto it = pos[t].insert(x); 
	int nxt = *next(it); 

	if(it == pos[t].begin()) { 
		Q.erase(Q.find(nxt)); 
		Q.insert(x); 		
	}

	update(1, 0, M, idx, nxt); 

	if(it != pos[t].begin()) {
		int prv = *prev(it); 
		idx = lower_bound(v.begin(), v.end(), prv) - v.begin(); 
		update(1, 0, M, idx, x); 
	}	
} 

void removePoint(int x, int t) {
	int idx = lower_bound(v.begin(), v.end(), x) - v.begin();	
	
	auto it = pos[t].find(x); 
	int nxt = *next(it); 

	if(it == pos[t].begin()) {
		Q.erase(Q.find(x)); 
		Q.insert(nxt); 
	}

	update(1, 0, M, idx, 0); 

	if(it != pos[t].begin()) {
		int prv = *prev(it); 
		idx = lower_bound(v.begin(), v.end(), prv) - v.begin(); 
		update(1, 0, M, idx, nxt); 
	}

	pos[t].erase(it);
}

bool check(int l, int r) {
	if(l < 1) return 1; 
	int idx = lower_bound(v.begin(), v.end(), l) - v.begin(); 
	while(v[idx] >= l) --idx; 
	return query(1, 0, M, 0, idx) <= r;
}

int solve(int x) {
	int fmax = *Q.rbegin(); 
	if(fmax == inf) return -1; 

	int lo = max(0, fmax - x), hi = max(x - 1, v.back() - x), ans = -1;

	while(lo <= hi) {
		int m = lo + hi >> 1; 
		if(check(x - m, x + m))
			ans = m, hi = m - 1; 
		else lo = m + 1; 
	}

	return ans; 
}

int main(int argc, char const *argv[]) {
	scanf("%d %d %d", &n, &k, &q);	
	for(int i = 1; i <= n; ++i) {
		int x, a, b, t; 
		scanf("%d %d %d %d", &x, &t, &a, &b); 
		E.emplace_back(x, a, t, 0);
		E.emplace_back(x, b + 1, t, -1);
		v.push_back(x); 
	}
	for(int i = 1; i <= q; ++i) {
		int l, y; 
		scanf("%d %d", &l, &y); 
		E.emplace_back(l, y, -1, i); 
		v.push_back(l); 
	}

	sort(v.begin(), v.end()); 
	sort(E.begin(), E.end()); 
	v.erase(unique(v.begin(), v.end()), v.end()); 

	M = v.size() + 2; 
	tree = vector<int>(4 * M, 0); 

	for(int i = 1; i <= k; ++i) {
		pos[i].insert(inf); 
		Q.insert(inf); 
	}

	for(auto e : E) {
		if(e.id == 0) {
			addPoint(e.x, e.t);	
		} else if(e.id == -1) {	
			removePoint(e.x, e.t); 
		} else {
			ans[e.id] = solve(e.x);
		}
	}

	for(int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

new_home.cpp: In function 'void update(int, int, int, int, int)':
new_home.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1; 
          ~~^~~
new_home.cpp: In function 'int query(int, int, int, int, int)':
new_home.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1; 
          ~~^~~
new_home.cpp: In function 'int solve(int)':
new_home.cpp:96:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = lo + hi >> 1; 
           ~~~^~~~
new_home.cpp: In function 'int main(int, const char**)':
new_home.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &t, &a, &b); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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