oj.uz

답안 #83241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83241 2018-11-06T10:14:56 Z farukkastamonuda 새 집 (APIO18_new_home) C++14
0 / 100
 1204 ms 45800 KB 
#include <bits/stdc++.h>
#define li 300005
#define inf 1000000009
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define iii pair< pair<int,int> ,int >
using namespace std;
int n,k,qq,x,t,l,r,kon,y,tut[li],say,cev[li],son;
pair< pair<int,int> , pair<int,int> > p[li];
pair<int , pair<int,int> > q[li];
set < pair<int,int> > sil;
set < pair< pair<int , int> , int > > st;
int main(){
	scanf("%d %d %d",&n,&k,&qq);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d %d",&x,&t,&l,&r);
		p[i]=mp(mp(l,r),mp(x,t));
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=qq;i++){
		scanf("%d %d",&kon,&y);
		q[i]=mp(y,mp(kon,i));
	}
	sort(q+1,q+qq+1);
	for(int i=1;i<=n;i++){
		if(p[i].fi.fi<=q[1].fi){
			son=i+1;
		}
		if(p[i].fi.fi<=q[1].fi && p[i].fi.se>=q[1].fi){
			//printf("?%d\n",i);
			st.insert(mp(mp(p[i].se.fi,p[i].se.se),i));
			sil.insert(mp(p[i].fi.se,i));
			if(tut[p[i].se.se]==0){
				tut[p[i].se.se]=1;
				say++;
			}
			else{
				tut[p[i].se.se]++;
			}
		}
	}
	//printf("YYYY\n");
	for(int i=1;i<=qq;i++){
		//printf("YYYY\n");
		if(say!=k){
			cev[q[i].se.se]=-1;
			//printf("KACKEZ\n");
		}
		else{
			//printf("37\n");
			auto it=st.end();
			//cout<<"size:: :: "<<(int)st.size()<<endl;
			//printf("42\n");
			it--;
			//printf("63\n");
			iii tmp=*it;
			int cev1=-1,val=tmp.fi.fi,cev2=-1;
			//printf("OLDU MU \n");
			//~ if(q[i].se.fi<=val){
				//~ auto gg=st.lower_bound(mp(mp(q[i].se.fi,0),0));
				//~ tmp=*gg;
				//~ cev1=abs(tmp.fi.fi-q[i].se.fi);
				//~ if(gg!=st.begin()){
					//~ gg--;
					//~ tmp=*gg;
					//~ cev2=abs(tmp.fi.fi-q[i].se.fi);
				//~ }
			//~ }
			//~ else{
				//~ auto gg=st.end();
				//~ gg--;
				//~ tmp=*gg;
				//~ cev1=abs(q[i].se.fi-tmp.fi.fi);
			//~ }
			cev1=abs(q[i].se.fi-val);
			it=st.begin();
			tmp=*it;
			cev2=abs(q[i].se.fi-tmp.fi.fi);
			cev[q[i].se.se]=max(cev1,cev2);
		}
		if(i==qq) break; 
		//printf("GHGH\n");
		auto tr=sil.lower_bound(mp(q[i+1].fi,-inf));
		if(tr!=sil.begin()){
			//tr--;
			vector< pair<int,int> > ty;
			for(auto h=sil.begin();h!=tr;h++){
				pair<int,int> hop=*h;
				int ii=hop.se;
				//if(i==1) printf("DEBUG - >> :: %d\n",ii);
				tut[p[ii].se.se]--;
				if(tut[p[ii].se.se]==0) say--;
				st.erase(mp(mp(p[ii].se.fi,p[ii].se.se),ii));
				//cout<<"YETER\n"<<(int)st.size()<<endl;
				//sil.erase(h);
				ty.pb(hop);
				//printf("(");
			}
			for(int j=0;j<(int)ty.size();j++) sil.erase(ty[j]);
		}
		if(i==qq) break;
		int flag=0;
		for(int j=son;j<=n;j++){
			if(p[j].fi.fi<=q[i+1].fi){
				if(p[j].fi.se>=q[i+1].fi){
					//if(i==1) printf("DEB- .> >> ::  :: %d\n",j);
					st.insert(mp(mp(p[j].se.fi,p[j].se.se),j));
					sil.insert(mp(p[j].fi.se,j));
					if(tut[p[j].se.se]==0){
						tut[p[j].se.se]=1;
						say++;
					}
					else tut[p[j].se.se]++;
				}
			}
			else{
				flag=1;
				son=j;
				break;
			}
		}
		if(flag==0) son=n+1;
		//printf("\nSAY:: :: %d\n",say);
	}
	for(int i=1;i<=qq;i++) printf("%d\n",cev[i]);
	return 0;
}
//~ 4 2 4
//~ 3 1 1 10
//~ 9 2 2 4
//~ 7 2 5 7
//~ 4 1 8 10
//~ 5 3
//~ 5 6
//~ 5 9
//~ 1 10

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&k,&qq);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&x,&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&kon,&y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 456 KB Output isn't correct
5 Halted 0 ms 0 KB -