Submission #554547

#	Time	Username	Problem	Language	Result	Execution time	Memory
554547		nafis_shifat	New Home (APIO18_new_home)	C++17	0 / 100	2528 ms	80692 KiB

new_home

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=6e5+5;
const int inf=1e9;
const int MX = 3e5 + 1;
struct segtree {
	int tree[4*mxn];
	void update(int node,int b,int e,int p,int v) {
		if(e < p || b > p)return;
		if(b == e) {
			tree[node] = v;
			return;
		}

		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node]=max(tree[left],tree[right]);
	}

	int query(int node, int b, int e, int l, int r) {
		if(e < l || b > r) return 0;

		if(b >= l && e <= r) return tree[node];
		int mid = b + e >> 1;
		int left = node << 1;
		int right = left | 1;

		return max(query(left, b, mid, l, r), query(right, mid + 1, e , l, r));
	}

} st;


ll x[mxn];
int tp[mxn];

ll p[mxn], y[mxn];
multiset<ll> con[mxn];
vector<ll> v;


int main() {
	int n, k, q;
	cin >> n >> k >> q;

	for(int i = 1; i <= k; i++) {
		x[i] = -inf + i;
		tp[i] = i;
		v.push_back(x[i]);
		con[tp[i]].insert(x[i]);
		con[tp[i]].insert(inf);
	}

	for(int i = k; i < n + k; i++) {
		int a, b;
		scanf("%lld %d%d%d", &x[i], &tp[i], &a, &b);
		v.push_back(x[i]);
		con[tp[i]].insert(x[i]);

	}

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



	for(int i = 1; i <= k; i++) {

		auto it = con[i].begin();
		it++;

		for(;it != con[i].end(); it++) {
			int prv = *prev(it);
			int cr = *it;

			int lp = lower_bound(v.begin(), v.end(), prv) - v.begin() + 1;
			st.update(1, 1, MX, lp, cr);
		}
	}


	for(int i = 1; i <= q; i++) {
		scanf("%lld %lld", &p[i], &y[i]);




		int lo = 0;
		int hi = (int) inf;
		ll ans = -1;
		while(lo <= hi) {
			int mid = lo + hi >> 1;

			int pos = p[i] - mid;

			int d = lower_bound(v.begin(), v.end(), pos) - v.begin();


			if(st.query(1, 1, MX, 1, d) <= p[i] + mid) {
				ans = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}

		cout<<ans<<endl;
	}



	









	
}

Compilation message (stderr)

new_home.cpp: In member function 'void segtree::update(int, int, int, int, int)':
new_home.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int mid=b+e>>1;
      |           ~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int, int)':
new_home.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = b + e >> 1;
      |             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |    int mid = lo + hi >> 1;
      |              ~~~^~~~
new_home.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%lld %d%d%d", &x[i], &tp[i], &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%lld %lld", &p[i], &y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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