Submission #251863

#	Time	Username	Problem	Language	Result	Execution time	Memory
251863		oolimry	New Home (APIO18_new_home)	C++14	33 / 100	1843 ms	86956 KiB

new_home

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define X first
#define T second
using namespace std;
typedef pair<int,int> ii;
typedef map<ii, int>::iterator iter;
const int MAXN = 300005;
const int INF = 2e8;

int n, K, Q, sz;
struct store { int X, id, T; };
struct query { int X, id, T, ans; };
struct line { int start, xintercept, open, close; }; ///line exists in time frame [open, close)

vector<store> stores[MAXN];
vector<query> queries;

struct segmenttree{
	vector<int> tree;
	void init(){
		tree.assign(2*sz,0);
	}
	
	void update(int l, int r, int v){
		for(l += sz, r += sz;l < r;l >>= 1, r >>= 1){
			if(l&1){
				tree[l] = max(tree[l], v);
				l++;
			}
			if(r&1){
				r--;
				tree[r] = max(tree[r], v);
			}
		}
	}
	
	int query(int i){
		int res = 0;
		for(i += sz;i > 0;i >>= 1) res = max(res, tree[i]);
		return res;
	}
};

map<ii, int> open; ///map<ii(location, index), time>
void solve(){
	vector<line> lines;
	
	for(int type = 1;type <= K;type++){
		open.clear();
		open[ii(-INF,0)] = 0;
		open[ii(INF,0)] = 0;
		
		for(store S : stores[type]){
			ii search = ii(S.X, S.id);
			iter cur = open.find(search);
			
			if(cur == open.end()){ ///S is going to be opened
				iter nxt = open.upper_bound(search);
				iter pre = prev(nxt);
				int nxtX = (nxt->first).X;
				int preX = (pre->first).X;
				
				lines.push_back({(nxtX + preX + 1)/2, nxtX, nxt->T, S.T});  ///line between nxt and pre broken when S is added 
				
				nxt->second = S.T; ///see footnote
				open[search] = S.T;
			}
			else{ ///S is going to be closed
				iter nxt = next(cur);
				iter pre = prev(cur);
				int nxtX = (nxt->first).X;
				int curX = (cur->first).X;
				int preX = (pre->first).X;
				
				lines.push_back({(nxtX + curX + 1)/2, nxtX, nxt->T, S.T}); ///line between nxt and cur broken when S is removed
				lines.push_back({(curX + preX + 1)/2, curX, cur->T, S.T}); ///line between cur and pre broken when S is removed
				
				nxt->second = S.T; ///see footnote
				open.erase(cur);
			}
		}
		lines.push_back({0, 2*INF, open[ii(INF,0)], sz});
	}
	
	for(line L : lines){
	//	cout << L.start << " " << L.xintercept << " " << L.open << " " << L.close << "\n";
	}
	//cout << "\n\n";		
	
	segmenttree tree; tree.init();
	sort(all(lines), [&](line a, line b){ return a.start < b.start; });
	
	int lineptr = 0;
	
	for(query &q : queries){
		while(lineptr < (int)lines.size() && lines[lineptr].start <= q.X){
			line L = lines[lineptr];
			tree.update(L.open, L.close, L.xintercept);
			//cout << L.open << " "  << L.close << " " << L.xintercept << "L\n";
			lineptr++;
		}
		
		q.ans = max(q.ans, tree.query(q.T) - q.X);
		//cout << q.X << " " << q.T << " " << q.ans << " " << tree.query(q.T) << "Q\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K >> Q;
	
	vector<int> times;
	for(int i = 1;i <= n;i++){
		int X, type, A, B; cin >> X >> type >> A >> B;
		stores[type].push_back({X, i, A}); ///open
		stores[type].push_back({X, i, B+1}); ///close
		times.push_back(A);
		times.push_back(B+1);
	}
	
	sort(times.begin(), times.end());
	times.erase(unique(all(times)), times.end());
	sz = times.size();
	
	for(int type = 1;type <= K;type++){
		for(store &S : stores[type]){
			S.T = lower_bound(all(times), S.T) - times.begin();
			//cout << S.T << " " << S.X << "L\n";
		}
		sort(all(stores[type]), [&](store a, store b){
			return a.T < b.T; ///increasing X tiebreak by id
		});
	}
	
	queries.resize(Q);
	for(int i = 0;i < Q;i++){
		cin >> queries[i].X >> queries[i].T;
		queries[i].T = upper_bound(all(times), queries[i].T) - times.begin() - 1;
		//cout << queries[i].T << "T\n";
		queries[i].id = i;
		queries[i].ans = 0;
	}
	
	sort(all(queries), [&](query a, query b){ return a.X < b.X; });
	solve();
	
	for(query &q : queries) q.X = INF - q.X;
	reverse(all(queries));
	for(int type = 1;type <= K;type++){
		for(store &S : stores[type]) S.X = INF - S.X;
	}
	
	solve();
	
	sort(all(queries), [&](query a, query b){ return a.id < b.id; });
	for(query q : queries){
		if(q.ans >= INF) cout << "-1\n";
		else cout << q.ans << "\n";
	}
}

///footnote: it's kinda complicated... Basically by updating the right value, it's saying that any line which references the right range must start from the previous S->T

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:86:11: warning: variable 'L' set but not used [-Wunused-but-set-variable]
  for(line L : lines){
           ^

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