oj.uz

답안 #152220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152220 2019-09-06T20:23:33 Z TadijaSebez 새 집 (APIO18_new_home) C++11
0 / 100
 3746 ms 238964 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define l_type 0
#define r_type 1
const int N=300050;
const int mxx=1e8;
int x[N],t[N],a[N],b[N],qx[N],qt[N],n,q,k,ans[N],myl[N],myr[N];
struct cmp{ bool operator () (int i, int j) const { return x[i]<x[j] || (x[i]==x[j] && i<j);}};
set<int,cmp> house[N];
const int H=8*N;
int type[H],l[H],r[H],tl[H],tr[H],hsz;
int act[N],active,cur_time;
int Seg(int ty, int _l, int _r, int _tl){ hsz++;type[hsz]=ty;l[hsz]=_l;r[hsz]=_r;tl[hsz]=_tl;tr[hsz]=-1;return hsz;}
void S(int i, int j)
{
	if(i==0) myr[j]=Seg(r_type,1,x[j],cur_time);
	else if(j==0) myl[i]=Seg(l_type,x[i],mxx,cur_time);
	else
	{
        int mid=x[i]+x[j]>>1;
        myl[i]=Seg(l_type,x[i],mid,cur_time);
        myr[i]=Seg(r_type,mid+1,x[j],cur_time);
	}
}
void E(int i, int j)
{
	if(i!=0) tr[myl[i]]=cur_time-1;
	if(j!=0) tr[myr[j]]=cur_time-1;
}
void Add(int i)
{
	act[t[i]]++;if(act[t[i]]==1) active++;
	house[t[i]].insert(i);
	auto it=house[t[i]].find(i);
	bool lf=0,rf=0;
	auto L=it,R=it;
	if(L!=house[t[i]].begin()) L--,lf=1;
	R++;if(R!=house[t[i]].end()) rf=1;
	if(lf && rf) E(*L,*R),S(*L,i),S(i,*R);
	else if(lf) E(*L,0),S(*L,i),S(i,0);
	else if(rf) E(0,*R),S(i,*R),S(0,i);
	else S(0,i),S(i,0);
}
void Del(int i)
{
	act[t[i]]--;if(act[t[i]]==0) active--;
	auto it=house[t[i]].find(i);
	bool lf=0,rf=0;
	auto L=it,R=it;
	if(L!=house[t[i]].begin()) L--,lf=1;
	R++;if(R!=house[t[i]].end()) rf=1;
	if(lf && rf) E(*L,i),E(i,*R),S(*L,*R);
	else if(lf) E(*L,i),E(i,0),S(*L,0);
	else if(rf) E(i,*R),E(0,i),S(0,*R);
	else E(0,i),E(i,0);
	house[t[i]].erase(i);
}
vector<int> cmpr_time;
int get_time_id(int x){ return lower_bound(cmpr_time.begin(),cmpr_time.end(),x)-cmpr_time.begin();}
const int M=2*N;
vector<int> lst[M],rst[M];
int ls[M],rs[M],tsz,root,lim,l_ptr[M],r_ptr[M];
void Build(int &c, int ss, int se, vector<int> l_segs, vector<int> r_segs)
{
	c=++tsz;
	vector<int> l_push[2],r_push[2];
	int mid=ss+se>>1;
    for(int i:l_segs)
	{
		if(tl[i]<=cmpr_time[ss] && tr[i]>=cmpr_time[se]) lst[c].pb(i);
		else
		{
			if(tl[i]<=cmpr_time[mid]) l_push[0].pb(i);
			if(tr[i]>=cmpr_time[mid+1]) l_push[1].pb(i);
		}
	}
    for(int i:r_segs)
	{
		if(tl[i]<=cmpr_time[ss] && tr[i]>=cmpr_time[se]) rst[c].pb(i);
		else
		{
			if(tl[i]<=cmpr_time[mid]) r_push[0].pb(i);
			if(tr[i]>=cmpr_time[mid+1]) r_push[1].pb(i);
		}
	}
	if(ss==se) return;
	Build(ls[c],ss,mid,l_push[0],r_push[0]);
	Build(rs[c],mid+1,se,l_push[1],r_push[1]);
}
int GetL(int c, int ss, int se, int id)
{
	while(l_ptr[c]<lst[c].size() && r[lst[c][l_ptr[c]]]<qx[id]) l_ptr[c]++;
	int ans=l_ptr[c]==lst[c].size()?0:qx[id]-l[lst[c][l_ptr[c]]];
	if(ss==se) return ans;
	int mid=ss+se>>1;
	if(qt[id]<=cmpr_time[mid]) ans=max(ans,GetL(ls[c],ss,mid,id));
	else ans=max(ans,GetL(rs[c],mid+1,se,id));
	return ans;
}
int GetR(int c, int ss, int se, int id)
{
	while(r_ptr[c]<rst[c].size() && l[rst[c][r_ptr[c]]]>qx[id]) r_ptr[c]++;
	int ans=r_ptr[c]==rst[c].size()?0:r[rst[c][r_ptr[c]]]-qx[id];
	if(ss==se) return ans;
	int mid=ss+se>>1;
	if(qt[id]<=cmpr_time[mid]) ans=max(ans,GetR(ls[c],ss,mid,id));
	else ans=max(ans,GetR(rs[c],mid+1,se,id));
	return ans;
}
int main()
{
	scanf("%i %i %i",&n,&k,&q);
	vector<pair<int,int>> events;
	for(int i=1;i<=n;i++) scanf("%i %i %i %i",&x[i],&t[i],&a[i],&b[i]),events.pb({a[i],i}),events.pb({b[i]+1,-i});
	for(int i=1;i<=q;i++) scanf("%i %i",&qx[i],&qt[i]),events.pb({qt[i],n+i}),cmpr_time.pb(qt[i]);
	sort(cmpr_time.begin(),cmpr_time.end());
	cmpr_time.resize(unique(cmpr_time.begin(),cmpr_time.end())-cmpr_time.begin());
	sort(events.begin(),events.end());
	for(int i=0;i<events.size();i++)
	{
		int id=events[i].second;
		cur_time=events[i].first;
		if(id<0) Del(-id);
		else if(id<=n) Add(id);
		else if(active!=k) ans[id-n]=-1;
	}
	for(int i=1;i<=hsz;i++) if(tr[i]==-1) tr[i]=cur_time;
	vector<int> l_segs,r_segs;
	l_segs.reserve(hsz);
	r_segs.reserve(hsz);
	for(int i=1;i<=hsz;i++){ if(type[i]==l_type) l_segs.pb(i);else r_segs.pb(i);}
	sort(l_segs.begin(),l_segs.end(),[&](int i, int j){ return l[i]<l[j];});
	sort(r_segs.begin(),r_segs.end(),[&](int i, int j){ return r[i]>r[j];});
	lim=(int)cmpr_time.size()-1;
	Build(root,0,lim,l_segs,r_segs);
	vector<int> qs;
	for(int i=1;i<=q;i++) if(ans[i]!=-1) qs.pb(i);
	sort(qs.begin(),qs.end(),[&](int i, int j){ return qx[i]<qx[j];});
	for(int i:qs) ans[i]=GetL(root,0,lim,i);
	reverse(qs.begin(),qs.end());
	for(int i:qs) ans[i]=max(ans[i],GetR(root,0,lim,i));
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message

new_home.cpp: In function 'void S(int, int)':
new_home.cpp:21:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=x[i]+x[j]>>1;
                 ~~~~^~~~~
new_home.cpp: In function 'void Build(int&, int, int, std::vector<int>, std::vector<int>)':
new_home.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int GetL(int, int, int, int)':
new_home.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l_ptr[c]<lst[c].size() && r[lst[c][l_ptr[c]]]<qx[id]) l_ptr[c]++;
        ~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int ans=l_ptr[c]==lst[c].size()?0:qx[id]-l[lst[c][l_ptr[c]]];
          ~~~~~~~~^~~~~~~~~~~~~~~
new_home.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int GetR(int, int, int, int)':
new_home.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(r_ptr[c]<rst[c].size() && l[rst[c][r_ptr[c]]]>qx[id]) r_ptr[c]++;
        ~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int ans=r_ptr[c]==rst[c].size()?0:r[rst[c][r_ptr[c]]]-qx[id];
          ~~~~~~~~^~~~~~~~~~~~~~~
new_home.cpp:106:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:120:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<events.size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:115:88: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i %i %i",&x[i],&t[i],&a[i],&b[i]),events.pb({a[i],i}),events.pb({b[i]+1,-i});
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:116:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&qx[i],&qt[i]),events.pb({qt[i],n+i}),cmpr_time.pb(qt[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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