Submission #1014138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014138	2024-07-04T12:14:40 Z	pcc	New Home (APIO18_new_home)	C++17	10 / 100	1008 ms	147008 KB

new_home

#include <bits/stdc++.h>
using namespace std;


#define _all(T) T.begin(),T.end()
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6;
const int inf = 1e9;
const int lim = 1e8+10;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	int seg[mxn*4];
	SEG(){
		fill(seg,seg+mxn*4,-inf);
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now] = max(seg[now],v);
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		return;
	}
	int getval(int now,int l,int r,int p){
		if(l == r)return seg[now];
		if(mid>=p)return max(seg[now],getval(ls,l,mid,p));
		else return max(seg[now],getval(rs,mid+1,r,p));
	}
#undef mid
#undef ls
#undef rs
};

SEG seg1,seg2;
int N,K,Q;
set<int> st[mxn];
vector<int> all;
vector<pii> req;
array<int,4> shop[mxn];

int main(){
	cin>>N>>K>>Q;
	for(int i = 1;i<=N;i++){
		cin>>shop[i][0]>>shop[i][1]>>shop[i][2]>>shop[i][3];//x,t,a,b
		all.push_back(shop[i][0]);
	}
	for(int i = 0;i<Q;i++){
		int l,y;
		cin>>l>>y;
		all.push_back(l);
		req.push_back(pii(l,y));
	}
	all.push_back(-inf);all.push_back(inf);
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	for(int i = 1;i<=K;i++){
		st[i].insert(0);
		st[i].insert(all.size()-1);
	}
	for(int i = 1;i<=N;i++){
		shop[i][0] = lower_bound(_all(all),shop[i][0])-all.begin();
		st[shop[i][1]].insert(shop[i][0]);
	}
	for(int i = 1;i<=K;i++){
		for(auto it = ++st[i].begin();it != st[i].end();it++){
			int l = *prev(it),r = *it;
			int mid = all[l]+(all[r]-all[l])/2;
			auto pos = upper_bound(_all(all),mid)-all.begin();
			seg1.modify(0,0,all.size(),l,pos-1,-all[l]);
			seg2.modify(0,0,all.size(),pos,r,all[r]);
		}
	}
	for(auto [pos,_] : req){
		pos = lower_bound(_all(all),pos)-all.begin();
		int ans = max(all[pos]+seg1.getval(0,0,all.size(),pos),seg2.getval(0,0,all.size(),pos)-all[pos]);
		cout<<(ans>=lim?-1:ans)<<'\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	78672 KB	Output is correct
2	Incorrect	30 ms	78676 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	78672 KB	Output is correct
2	Incorrect	30 ms	78676 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1008 ms	117676 KB	Output is correct
2	Correct	777 ms	115500 KB	Output is correct
3	Correct	977 ms	146988 KB	Output is correct
4	Correct	865 ms	127792 KB	Output is correct
5	Correct	745 ms	115872 KB	Output is correct
6	Correct	778 ms	116012 KB	Output is correct
7	Correct	809 ms	147008 KB	Output is correct
8	Correct	833 ms	127864 KB	Output is correct
9	Correct	828 ms	121132 KB	Output is correct
10	Correct	761 ms	117284 KB	Output is correct
11	Correct	617 ms	116012 KB	Output is correct
12	Correct	704 ms	117036 KB	Output is correct