oj.uz

Submission #289743

# Submission time Handle Problem Language Result Execution time Memory
289743 2020-09-03T02:17:53 Z Takaya Yuta(#5796) None (JOI12_invitation) C++17
100 / 100
 1786 ms 121552 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define SIZE 100005
#define BT 128*1024*4*2

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct seg1
{
	int seg[BT+5],pos[BT+5];
	int add[BT+5];
	bool good[BT+5];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++)
		{
			seg[i]=add[i]=pos[i]=-1;
			good[i]=true;
		}
	}
	void pass(int k,int l,int r)
	{
		for(int i=k*2+1;i<=k*2+2;i++)
		{
			if(add[k]>add[i])
			{
				add[i]=add[k];
				if(seg[i]<add[k])
				{
					seg[i]=add[k];
					pos[i]=i==k*2+1?l:(l+r)/2;
				}
			}
		}
	}
	void make(int k)
	{
		good[k]=good[k*2+1]||good[k*2+2];
		seg[k]=pos[k]=-1;
		if(good[k*2+1]&&seg[k*2+1]>=seg[k*2+2])
		{
			seg[k]=seg[k*2+1];
			pos[k]=pos[k*2+1];
		}
		else if(good[k*2+2])
		{
			seg[k]=seg[k*2+2];
			pos[k]=pos[k*2+2];
		}
	}
	void update(int a,int b,int k,int l,int r,int v)
	{
		if(b<=l||r<=a||!good[k]) return;
		if(a<=l&&r<=b)
		{
			if(add[k]<v)
			{
				add[k]=v;
				if(seg[k]<v)
				{
					seg[k]=v;
					pos[k]=l;
				}
			}
		}
		else
		{
			pass(k,l,r);
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
			make(k);
		}
	}
	void update(int a,int b,int v)
	{
		update(a,b,0,0,mum,v);
	}
	void rem(int k)
	{
		int l=0,r=mum,nk=0;
		while(l+1<r)
		{
			pass(nk,l,r);
			if(k<(l+r)/2)
			{
				r=(l+r)/2;
				nk=nk*2+1;
			}
			else
			{
				l=(l+r)/2;
				nk=nk*2+2;
			}
		}
		seg[nk]=pos[nk]=add[nk]=-1;
		good[nk]=false;
		while(nk>0)
		{
			nk=(nk-1)/2;
			make(nk);
		}
	}
	P get()
	{
		return P(seg[0],pos[0]);
	}
	void see()
	{
		for(int i=mum-1;i<mum*2;i++) printf("%d ",good[i]);
		puts("");
	}
};
struct seg2
{
	vector <int> vec[BT+5];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
	}
	void update(int a,int b,int k,int l,int r,int v)
	{
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b) vec[k].push_back(v);
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
		}
	}
	void update(int a,int b,int v)
	{
		update(a,b,0,0,mum,v);
	}
	vector <int> get(int k)
	{
		k+=mum-1;
		vector <int> ret=vec[k];
		vec[k].clear();
		while(k>0)
		{
			k=(k-1)/2;
			ret.insert(ret.end(),vec[k].begin(),vec[k].end());
			vec[k].clear();
		}
		return ret;
	}
};
seg1 d1,c1;
seg2 d2,c2;
bool use[SIZE],du[SIZE*4],cu[SIZE*4];
vector <int> vx,vy;
vector <P> dog,cat;
int p[SIZE],q[SIZE],r[SIZE],s[SIZE],t[SIZE];

int dogs(int x)
{
	return lower_bound(dog.begin(),dog.end(),P(x,-1))-dog.begin();
}
int cats(int x)
{
	return lower_bound(cat.begin(),cat.end(),P(x,-1))-cat.begin();
}
void dogin(int c)
{
	vector <int> vec;
	vec=d2.get(c);
	for(int i=0;i<vec.size();i++)
	{
		int v=vec[i];
		if(use[v]) continue;
		use[v]=true;
		d1.update(p[v],q[v]+1,t[v]);
		c1.update(r[v],s[v]+1,t[v]);
	}
}
void catin(int c)
{
	vector <int> vec;
	vec=c2.get(c);
	for(int i=0;i<vec.size();i++)
	{
		int v=vec[i];
		if(use[v]) continue;
		use[v]=true;
		d1.update(p[v],q[v]+1,t[v]);
		c1.update(r[v],s[v]+1,t[v]);
	}
}
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d %d",&p[i],&q[i],&r[i],&s[i],&t[i]);
		vx.push_back(p[i]);
		vx.push_back(q[i]);
		vy.push_back(r[i]);
		vy.push_back(s[i]);
	}
	vx.push_back(c);
	sort(vx.begin(),vx.end());
	sort(vy.begin(),vy.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	vy.erase(unique(vy.begin(),vy.end()),vy.end());
	for(int i=0;i<vx.size();i++)
	{
		dog.push_back(P(vx[i],1));
		if(i+1<vx.size()&&vx[i+1]-vx[i]>=2) dog.push_back(P(vx[i]+1,vx[i+1]-vx[i]-1));
	}
	for(int i=0;i<vy.size();i++)
	{
		cat.push_back(P(vy[i],1));
		if(i+1<vy.size()&&vy[i+1]-vy[i]>=2) cat.push_back(P(vy[i]+1,vy[i+1]-vy[i]-1));
	}
	d1.init(dog.size()+2);d2.init(dog.size()+2);
	c1.init(cat.size()+2);c2.init(cat.size()+2);
	for(int i=0;i<n;i++)
	{
		p[i]=dogs(p[i]);q[i]=dogs(q[i]);
		r[i]=cats(r[i]);s[i]=cats(s[i]);
		d2.update(p[i],q[i]+1,i);
		c2.update(r[i],s[i]+1,i);
	}
	c=dogs(c);
	dogin(c);
	d1.rem(c);
	ll ret=0;
	int cd=1,cc=0;
	while(1)
	{
		P pd=d1.get(),pc=c1.get();
		//printf("%d %d %d %d\n",pd.first,pd.second,pc.first,pc.second);
		if(pd.first==-1&&pc.first==-1) break;
		if(pd.first>=pc.first)
		{
			ret+=(ll) pd.first;
			dogin(pd.second);
			if(dog[pd.second].second==1||du[pd.second])
			{
				d1.rem(pd.second);
				cd+=dog[pd.second].second;
				ret+=(ll) pd.first*(ll) (dog[pd.second].second-1-du[pd.second]);
			}
			else du[pd.second]=true;
		}
		else
		{
			ret+=(ll) pc.first;
			catin(pc.second);
			if(cat[pc.second].second==1||cu[pc.second])
			{
				c1.rem(pc.second);
				cc+=cat[pc.second].second;
				ret+=(ll) pc.first*(ll) (cat[pc.second].second-1-cu[pc.second]);
			}
			else cu[pc.second]=true;
		}
	}
	if(cd==a&&cc==b) printf("%lld\n",ret);
	else puts("-1");
	return 0;
}

Compilation message

invitation.cpp: In function 'void dogin(int)':
invitation.cpp:178:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  for(int i=0;i<vec.size();i++)
      |              ~^~~~~~~~~~~
invitation.cpp: In function 'void catin(int)':
invitation.cpp:191:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |  for(int i=0;i<vec.size();i++)
      |              ~^~~~~~~~~~~
invitation.cpp: In function 'int main()':
invitation.cpp:219:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |  for(int i=0;i<vx.size();i++)
      |              ~^~~~~~~~~~
invitation.cpp:222:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |   if(i+1<vx.size()&&vx[i+1]-vx[i]>=2) dog.push_back(P(vx[i]+1,vx[i+1]-vx[i]-1));
      |      ~~~^~~~~~~~~~
invitation.cpp:224:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |  for(int i=0;i<vy.size();i++)
      |              ~^~~~~~~~~~
invitation.cpp:227:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |   if(i+1<vy.size()&&vy[i+1]-vy[i]>=2) cat.push_back(P(vy[i]+1,vy[i+1]-vy[i]-1));
      |      ~~~^~~~~~~~~~
invitation.cpp:203:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  203 |  scanf("%d %d %d",&a,&b,&c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
invitation.cpp:205:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  205 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
invitation.cpp:208:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  208 |   scanf("%d %d %d %d %d",&p[i],&q[i],&r[i],&s[i],&t[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49664 KB Output is correct
2 Correct 32 ms 49664 KB Output is correct
3 Correct 31 ms 49664 KB Output is correct
4 Correct 31 ms 49664 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49792 KB Output is correct
2 Correct 32 ms 49664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 50040 KB Output is correct
2 Correct 33 ms 49788 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50812 KB Output is correct
2 Correct 46 ms 50816 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 50808 KB Output is correct
2 Correct 45 ms 50808 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1709 ms 121428 KB Output is correct
2 Correct 238 ms 54900 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1786 ms 119880 KB Output is correct
2 Correct 1078 ms 116860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1663 ms 121552 KB Output is correct
2 Correct 235 ms 54884 KB Output is correct
3 Correct 904 ms 88668 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1615 ms 117200 KB Output is correct
2 Correct 1059 ms 116688 KB Output is correct
3 Correct 801 ms 87768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 55904 KB Output is correct
2 Correct 1356 ms 101200 KB Output is correct
3 Correct 1637 ms 117200 KB Output is correct