oj.uz

답안 #53256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53256 2018-06-29T05:58:21 Z zetapi 새 집 (APIO18_new_home) C++14
10 / 100
 3762 ms 1089692 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e7;
const int INF=1e8;
 
struct data
{
	int val;
	int left;
	int right;
}  	seg[MAX],seg_[MAX];

multiset<int> st[MAX];
multiset<int> itr it,nxt,pre;

vector<int> vec[MAX];

vector<pii> order;

vector< pair<int,pii> > ask;

int N,K,Q,X,Y,n,t,timer,timers,ptr,type[MAX],loc[MAX],res[MAX];
 
int get(int X,int Y)
{
	return Y-X;
}
 
int gets(int X,int Y)
{
	if(!Y)
		return 0;
	return X-Y;
}
 
void UpdateNeg(int low,int high,int node,int qlow,int delta)
{	
	if(low>high or qlow>high)
		return ;
	if(qlow<=low)
	{
		seg[node].val=max(seg[node].val,delta);
		return ;
	}
	if(!seg[node].left)
		seg[node].left=++timer;
	if(!seg[node].right)
		seg[node].right=++timer;
	int mid=(low+high)/2;
	UpdateNeg(low,mid,seg[node].left,qlow,delta);
	UpdateNeg(mid+1,high,seg[node].right,qlow,delta);
	return ;
}
 
void UpdatePos(int low,int high,int node,int qhigh,int delta)
{
	if(low>high or low>qhigh)
		return ;
	if(high<=qhigh)
	{
		if(!seg_[node].val)
			seg_[node].val=delta;
		else
			seg_[node].val=min(seg_[node].val,delta);
		return ;
	}
	if(!seg_[node].left)
		seg_[node].left=++timers;
	if(!seg_[node].right)
		seg_[node].right=++timers;
	int mid=(low+high)/2;
	UpdatePos(low,mid,seg_[node].left,qhigh,delta);
	UpdatePos(mid+1,high,seg_[node].right,qhigh,delta);
	return ;
}
 
int QueryNeg(int low,int high,int node,int idx)
{
	if(!node)
		return 0;
	if(low==high)
		return get(idx,seg[node].val);
	int mid=(low+high)/2;
	if(idx>=low and idx<=mid)
		return max(get(idx,seg[node].val),QueryNeg(low,mid,seg[node].left,idx));
	else
		return max(get(idx,seg[node].val),QueryNeg(mid+1,high,seg[node].right,idx));
}
 
int QueryPos(int low,int high,int node,int idx)
{
	if(!node)
		return 0;
	if(low==high)
		return gets(idx,seg_[node].val);
	int mid=(low+high)/2;
	if(idx>=low and idx<=mid)
		return max(gets(idx,seg_[node].val),QueryPos(low,mid,seg_[node].left,idx));
	else
		return max(gets(idx,seg_[node].val),QueryPos(mid+1,high,seg_[node].right,idx));
}
 
void exclude(int ind)
{
	int CurType=type[ind],CurLoc=loc[ind];
	it=st[CurType].find(CurLoc);
	if(it==st[CurType].begin() and (++it)==st[CurType].end())
	{
		for(int A=1;A<=Q;A++)
			cout<<-1<<"\n";
		exit(0);
	}
	--it;
	if(it==st[CurType].begin())
	{
		nxt=it;
		++nxt;
		UpdateNeg(1,n,1,1,*nxt);
		st[CurType].erase(it);
	}
	else if((++it)==st[CurType].end())
	{
		--it;
		pre=it;
		--pre;
		UpdatePos(1,n,1,n,*pre);
		st[CurType].erase(it);
	}
	else
	{
		pre=it;
		nxt=it;
		--pre;
		++nxt;
		UpdatePos(1,n,1,(*pre+*nxt)/2,*pre);
		UpdateNeg(1,n,1,(*pre+*nxt+1)/2,*nxt);	
		st[CurType].erase(it);
	}
	return ;
}

signed main()
{
	ios_base::sync_with_stdio(false);
 
	n=INF;
	timer=1;
	timers=1;
	cin>>N>>K>>Q;
	for(int A=1;A<=N;A++)
	{
		cin>>loc[A]>>type[A]>>X>>X;
		vec[type[A]].pb(loc[A]);
		st[type[A]].insert(loc[A]);
		order.pb(mp(X,A));
	}
	sort(order.begin(),order.end());
	for(int A=1;A<=K;A++)
	{
		if(vec[A].empty())
		{
			while(Q--)
				cout<<-1<<"\n";
			return 0;
		}
		sort(vec[A].begin(),vec[A].end());
		for(int B=1;B<vec[A].size();B++)
			UpdateNeg(1,n,1,(vec[A][B]+vec[A][B-1]+1)/2,vec[A][B]);
		for(int B=0;B<vec[A].size()-1;B++)
			UpdatePos(1,n,1,(vec[A][B]+vec[A][B+1])/2,vec[A][B]);
		UpdateNeg(1,n,1,1,*vec[A].begin());
		UpdatePos(1,n,1,n,vec[A].back());
	}
	for(int A=1;A<=Q;A++)
	{
		cin>>X>>Y;
		ask.pb(mp(Y,mp(X,A)));
	}
	sort(ask.begin(),ask.end());
	for(auto A:ask)
	{
		while(ptr<order.size() and order[ptr].first<A.first)
		{
			exclude(order[ptr].second);
			++ptr;
		}
		res[A.second.second]=max(QueryPos(1,n,1,A.second.first),QueryNeg(1,n,1,A.second.first));
	}
	for(int A=1;A<=Q;A++)
		cout<<res[A]<<"\n";
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:175:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=0;B<vec[A].size()-1;B++)
               ~^~~~~~~~~~~~~~~~
new_home.cpp:190:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<order.size() and order[ptr].first<A.first)
         ~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 704888 KB Output is correct
2 Correct 615 ms 704996 KB Output is correct
3 Correct 581 ms 705184 KB Output is correct
4 Incorrect 591 ms 705184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 704888 KB Output is correct
2 Correct 615 ms 704996 KB Output is correct
3 Correct 581 ms 705184 KB Output is correct
4 Incorrect 591 ms 705184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2499 ms 928464 KB Output is correct
2 Correct 2423 ms 965232 KB Output is correct
3 Correct 1174 ms 965232 KB Output is correct
4 Correct 2401 ms 965232 KB Output is correct
5 Correct 2435 ms 975732 KB Output is correct
6 Correct 2471 ms 975732 KB Output is correct
7 Correct 976 ms 975732 KB Output is correct
8 Correct 2071 ms 975732 KB Output is correct
9 Correct 2464 ms 975732 KB Output is correct
10 Correct 2544 ms 975732 KB Output is correct
11 Correct 1790 ms 975732 KB Output is correct
12 Correct 2150 ms 975732 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 704888 KB Output is correct
2 Correct 615 ms 704996 KB Output is correct
3 Correct 581 ms 705184 KB Output is correct
4 Incorrect 591 ms 705184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 704888 KB Output is correct
2 Correct 615 ms 704996 KB Output is correct
3 Correct 581 ms 705184 KB Output is correct
4 Incorrect 591 ms 705184 KB Output isn't correct
5 Halted 0 ms 0 KB -