oj.uz

답안 #203837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203837 2020-02-22T13:48:46 Z Segtree 새 집 (APIO18_new_home) C++14
0 / 100
 5000 ms 224784 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 600010
ll dat[2*N];
void init(){
	rep(i,2*N)dat[i]=-1e17;
}
void upd(ll i,ll x){
	i+=N,dat[i]=x;
	for(;i;i>>=1)dat[i/2]=max(dat[i],dat[i^1]);
}
ll qry(ll l,ll r){
	l+=N,r+=N;
	ll res=-1e17;
	for(ll a=l,b=r;a<b;a>>=1,b>>=1){
		if(a&1)chmax(res,dat[a++]);
		if(b&1)chmax(res,dat[--b]);
	}
	return res;
}

struct st{
	ll tim,typ,c,d;
	bool operator<(const st&key)const{
		if(this->tim==key.tim){
			return this->typ<key.typ;
		}
		return this->tim<key.tim;
	}
};
ll n,q,k,x[N],t[N],a[N],b[N],fans[N];
multiset<ll> s[N];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>k>>q;
	vector<pair<ll,ll> > xs;
	rep(i,n){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		t[i]--;
		xs.push_back(make_pair(x[i],i));
	}
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	vector<st> v;
	rep(i,n){
		pair<ll,ll> key=make_pair(x[i],i);
		x[i]=lower_bound(xs.begin(),xs.end(),key)-xs.begin();
		v.push_back((struct st){a[i],0,x[i]+k,t[i]});
		v.push_back((struct st){b[i],2,x[i]+k,t[i]});
	}
	rep(i,q){
		ll l,y; cin>>l>>y;
		v.push_back((struct st){y,1,l,i});
	}
	sort(v.begin(),v.end());
	init();
	rep(i,k){
		s[i].insert(i);
		s[i].insert(1e17);
		upd(i,1e17);
	}
	for(auto e:v){
		if(e.typ==0){
			ll place=e.c,col=e.d;
			auto it=s[col].upper_bound(place);
			ll r=*it;
			it--;
			ll l=*it;
			upd(l,place);
			upd(place,r);
			s[col].insert(place);
		}
		if(e.typ==1){
			cout<<"qry"<<e.c<<" "<<e.d<<endl;
			rep(i,k){
				cout<<i<<":";
				for(auto val:s[i])cout<<val<<" ";
				cout<<endl;
			}
			ll place=e.c,id=e.d;
			ll L=-1,R=1e9,mid;
			while(L<R-1){
				mid=(L+R)>>1;
				pair<ll,ll> key;
				key=make_pair(place-mid,-1e17);
				ll l=lower_bound(xs.begin(),xs.end(),key)-xs.begin()+k;
				key=make_pair(place+mid,+1e17);
				ll r=upper_bound(xs.begin(),xs.end(),key)-xs.begin()-1+k;
				if(qry(0,l)<=r)R=mid;
				else L=mid;
			}
			if(R==1e9)R=-1;
			fans[id]=R;
		}
		if(e.typ==2){
			ll place=e.c,col=e.d;
			s[col].erase(s[col].find(place));
			auto it=s[col].upper_bound(place);
			ll r=*it;
			it--;
			ll l=*it;
			upd(place,-1e17);
			upd(l,r);
		}
	}
	rep(i,q)cout<<fans[i]<<"\n";
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5063 ms 198252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5054 ms 224784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -