oj.uz

Submission #251863

# Submission time Handle Problem Language Result Execution time Memory
251863 2020-07-22T13:03:20 Z oolimry New Home (APIO18_new_home) C++14
33 / 100
 1843 ms 86956 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Incorrect 4 ms 7424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Incorrect 4 ms 7424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 70776 KB Output is correct
2 Correct 965 ms 66632 KB Output is correct
3 Correct 780 ms 86956 KB Output is correct
4 Correct 763 ms 70668 KB Output is correct
5 Correct 1601 ms 76800 KB Output is correct
6 Correct 1127 ms 67344 KB Output is correct
7 Correct 735 ms 86952 KB Output is correct
8 Correct 656 ms 69640 KB Output is correct
9 Correct 676 ms 68592 KB Output is correct
10 Correct 865 ms 66532 KB Output is correct
11 Correct 767 ms 65268 KB Output is correct
12 Correct 760 ms 67340 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 68236 KB Output is correct
2 Correct 765 ms 58544 KB Output is correct
3 Correct 1293 ms 66064 KB Output is correct
4 Correct 1075 ms 86708 KB Output is correct
5 Correct 1010 ms 70480 KB Output is correct
6 Correct 986 ms 70404 KB Output is correct
7 Correct 1843 ms 76568 KB Output is correct
8 Correct 1364 ms 67012 KB Output is correct
9 Correct 960 ms 86864 KB Output is correct
10 Correct 947 ms 69904 KB Output is correct
11 Correct 962 ms 68028 KB Output is correct
12 Correct 1122 ms 65704 KB Output is correct
13 Correct 877 ms 64836 KB Output is correct
14 Correct 885 ms 65400 KB Output is correct
15 Correct 939 ms 64840 KB Output is correct
16 Correct 971 ms 68924 KB Output is correct
17 Correct 1018 ms 65612 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Incorrect 4 ms 7424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Incorrect 4 ms 7424 KB Output isn't correct
5 Halted 0 ms 0 KB -