oj.uz

Submission #1014133

# Submission time Handle Problem Language Result Execution time Memory
1014133 2024-07-04T11:57:52 Z pcc New Home (APIO18_new_home) C++17
0 / 100
 912 ms 119600 KB 
#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;

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;

int main(){
	cin>>N>>K>>Q;
	for(int i = 1;i<=K;i++)st[i].insert(-inf);
	for(int i = 1;i<=K;i++)st[i].insert(inf);
	for(int i = 1;i<=N;i++){
		int x,t,a,b;
		cin>>x>>t>>a>>b;
		all.push_back(x);
		st[t].insert(x);
	}
	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++){
		for(auto it = ++st[i].begin();it != st[i].end();it++){
			int l = *prev(it),r = *it;
			int mid = l+(r-l)/2;
			l = lower_bound(_all(all),l)-all.begin();
			r = lower_bound(_all(all),r)-all.begin();
			auto pos = upper_bound(_all(all),mid)-all.begin();
			pos--;
			seg1.modify(0,0,all.size(),l,pos,-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>=1e8?-1:ans)<<'\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 119600 KB Output is correct
2 Incorrect 717 ms 111624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 874 ms 113708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -