Submission #1014139

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014139	2024-07-04T12:19:55 Z	pcc	New Home (APIO18_new_home)	C++17	10 / 100	1890 ms	797616 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];
	vector<vector<pii>> op;
	SEG(){
		fill(seg,seg+mxn*4,-inf);
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(!now)op.push_back({});
		op.back().push_back(pii(now,seg[now]));
		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;
	}
	void undo(){
		while(!op.back().empty()){
			auto [p,v] = op.back().back();
			op.back().pop_back();
			seg[p] = v;
		}
		op.pop_back();
		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 ans[mxn];
vector<pii> tseg[mxn*4];

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	56 ms	172884 KB	Output is correct
2	Incorrect	55 ms	172880 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	172884 KB	Output is correct
2	Incorrect	55 ms	172880 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	1465 ms	566012 KB	Output is correct
2	Correct	1024 ms	374176 KB	Output is correct
3	Correct	1890 ms	797616 KB	Output is correct
4	Correct	1528 ms	601148 KB	Output is correct
5	Correct	920 ms	371172 KB	Output is correct
6	Correct	1014 ms	372212 KB	Output is correct
7	Correct	1568 ms	797436 KB	Output is correct
8	Correct	1349 ms	599028 KB	Output is correct
9	Correct	1184 ms	541688 KB	Output is correct
10	Correct	1125 ms	457716 KB	Output is correct
11	Correct	879 ms	375076 KB	Output is correct
12	Correct	1044 ms	441708 KB	Output is correct