oj.uz

Submission #554574

# Submission time Handle Problem Language Result Execution time Memory
554574 2022-04-28T18:50:41 Z nafis_shifat New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 131192 KB 
#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;


int x[mxn];
int tp[mxn];
int a[mxn], b[mxn];

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

multiset<int> nxt[mxn];

int res[mxn];
void rmv(int p, int x) {
	nxt[p].erase(nxt[p].find(x));


	if(!nxt[p].empty()) st.update(1, 1, MX, p, *nxt[p].rbegin());
	else {
		st.update(1, 1, MX, p, inf);
	}


} 

void add(int p, int x) {
	nxt[p].insert(x);
	st.update(1, 1, MX, p, *nxt[p].rbegin());
}


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);
		nxt[i].insert(inf);
		st.update(1, 1, MX, i, inf);
	}


	vector<tuple<int,int,int>> ev;

	for(int i = k + 1; i <= n + k; i++) {
		scanf("%d%d%d%d", &x[i], &tp[i], &a[i], &b[i]);
		v.push_back(x[i]);
		ev.emplace_back(a[i], 0, i);
		ev.emplace_back(b[i], 2, i);

	}

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


	for(int i = 1; i <= q; i++) {
		scanf("%d %d", &p[i], &y[i]);
		ev.emplace_back(y[i], 1, i);
	}

	sort(ev.begin(), ev.end());


	for(auto [pos, t, id] : ev) {
		if(t == 0) {
			auto tmp = con[tp[id]].lower_bound(x[id] + 1);
			auto lst = prev(tmp);
			int lp = lower_bound(v.begin(), v.end(), *lst) - v.begin() + 1;
			rmv(lp, *tmp);
			add(lp, x[id]);
			int cp = lower_bound(v.begin(), v.end(), x[id]) - v.begin() + 1;
			add(cp, *tmp);
			con[tp[id]].insert(x[id]);
		} else if(t == 2) {
			auto tmp = con[tp[id]].lower_bound(x[id]);
			auto lst = prev(tmp);
			auto to = next(tmp);


			int lp = lower_bound(v.begin(), v.end(), *lst) - v.begin() + 1;
			int cp = lower_bound(v.begin(), v.end(), x[id]) - v.begin() + 1;

			rmv(lp, x[id]);
			nxt[cp].clear();
			st.update(1, 1, MX, cp, 0);
			add(lp, *to);
			con[tp[id]].erase(con[tp[id]].find(x[id]));
		} else {



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

				int pos = p[id] - mid;

				int d = lower_bound(v.begin(), v.end(), pos) - v.begin();
				assert(v[d - 1] < pos);


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

			res[id] = ans;
		}
	}

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



	
}

Compilation message

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:138:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
new_home.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d%d%d", &x[i], &tp[i], &a[i], &b[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d %d", &p[i], &y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56704 KB Output is correct
3 Correct 25 ms 56660 KB Output is correct
4 Correct 25 ms 56748 KB Output is correct
5 Execution timed out 5097 ms 56780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56704 KB Output is correct
3 Correct 25 ms 56660 KB Output is correct
4 Correct 25 ms 56748 KB Output is correct
5 Execution timed out 5097 ms 56780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 131192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 122764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56704 KB Output is correct
3 Correct 25 ms 56660 KB Output is correct
4 Correct 25 ms 56748 KB Output is correct
5 Execution timed out 5097 ms 56780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 25 ms 56704 KB Output is correct
3 Correct 25 ms 56660 KB Output is correct
4 Correct 25 ms 56748 KB Output is correct
5 Execution timed out 5097 ms 56780 KB Time limit exceeded
6 Halted 0 ms 0 KB -