제출 #341006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341006		ogibogi2004	Examination (JOI19_examination)	C++14	0 / 100	1998 ms	66128 KiB

examination

//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=3e5+6;
const ll SQRT=600;
ll n,q;
ll ans[MAXN];
set<pair<ll,ll> >xs;
set<ll>ys,zs;
ll s[MAXN],t[MAXN],sum[MAXN];
ll x[MAXN],y[MAXN],z[MAXN];
map<pair<ll,ll>,ll>newx;
map<ll,ll>newy,newz;
struct student
{
	ll a,b,c;
	student(){}
	student(ll _a,ll _b,ll _c)
	{
		a=_a;b=_b;c=_c;
	}
	bool operator<(student const& other)const
	{
		return b<other.b;
	}
};
struct query
{
	ll a,b,c,pos;
	query(){}
	query(ll _a,ll _b,ll _c,ll _pos)
	{
		a=_a;b=_b;c=_c;pos=_pos;
	}
	bool operator<(query const& other)const
	{
		return b<other.b;
	}
};
vector<student>blocks1[SQRT];
vector<query>blocks2[SQRT];
ll BIT[MAXN];
void update(ll idx,ll val)
{
	++idx;
	for(;idx<MAXN;idx+=idx&(-idx))
	{
		BIT[idx]+=val;
	}
}
ll query(ll idx)
{
	++idx;
	ll ret=0;
	for(;idx>0;idx-=idx&(-idx))
	{
		ret+=BIT[idx];
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>q;
	for(ll i=1;i<=n;++i)
	{
		cin>>s[i]>>t[i];
		xs.insert({s[i],i});
		sum[i]=s[i]+t[i];
		ys.insert(t[i]);zs.insert(sum[i]);
	}
	ll cntx=0,cnty=0,cntz=0;
	for(auto xd:xs)
	{
		newx[xd]=++cntx;
	}
	for(auto xd:ys)
	{
		newy[xd]=++cnty;
	}
	for(auto xd:zs)
	{
		newz[xd]=++cntz;
	}
	for(ll i=1;i<=q;++i)
	{
		cin>>x[i]>>y[i]>>z[i];
		xs.insert({x[i],-i});
		auto it=ys.lower_bound(y[i]);
		if(it==ys.end())y[i]=cnty+1;
		else y[i]=newy[(*it)];
		it=zs.lower_bound(z[i]);
		if(it==zs.end())z[i]=cntz+1;
		else z[i]=newz[(*it)];
	}
	for(auto xd:xs)
	{
		newx[xd]=++cntx;
	}
	for(ll i=1;i<=n;++i)
	{
		s[i]=newx[{s[i],i}];
		t[i]=newy[t[i]];
		sum[i]=newz[sum[i]];
	}
	for(ll i=1;i<=q;i++)
	{
		x[i]=newx[{x[i],-i}];
	}
	//cout<<"students:\n";
	for(ll i=1;i<=n;++i)
	{
		//cout<<s[i]<<" "<<t[i]<<" "<<sum[i]<<endl;
		blocks1[s[i]/SQRT].push_back({s[i],t[i],sum[i]});
	}
	//cout<<"criterias:\n";
	for(ll i=1;i<=q;++i)
	{
		//cout<<x[i]<<" "<<y[i]<<" "<<z[i]<<endl;
		blocks2[x[i]/SQRT].push_back({x[i],y[i],z[i],i});
	}
	vector<student>computed,eh,oh;
	for(ll j=SQRT-1;j>=0;--j)
	{
		if(blocks1[j].size()==0&&blocks2[j].size()==0)continue;
		memset(BIT,0,sizeof(BIT));
		/*cout<<"block1 "<<j<<":\n";
		for(ll i=0;i<blocks1[j].size();++i)
		{
			cout<<blocks1[j][i].a<<" "<<blocks1[j][i].b<<" "<<blocks1[j][i].c<<"\n";
		}
		cout<<endl;
		cout<<"block2 "<<j<<":\n";
		for(ll i=0;i<blocks2[j].size();++i)
		{
			cout<<blocks2[j][i].a<<" "<<blocks2[j][i].b<<" "<<blocks2[j][i].c<<" "<<blocks2[j][i].pos<<"\n";
		}
		cout<<endl;*/
		for(ll i1=0;i1<blocks2[j].size();++i1)
		{
			for(ll i2=0;i2<blocks1[j].size();++i2)
			{
				if(blocks2[j][i1].a<=blocks1[j][i2].a&&blocks2[j][i1].b<=blocks1[j][i2].b&&blocks2[j][i1].c<=blocks1[j][i2].c)
				{
					ans[blocks2[j][i1].pos]++;
				}
			}
		}
		sort(blocks2[j].rbegin(),blocks2[j].rend());
		ll p=computed.size()-1;
		for(ll i=0;i<blocks2[j].size();++i)
		{
			while(p>0&&computed[p].b>=blocks2[j][i].b)
			{
				update(computed[p].c,+1);
				p--;
			}
			ans[blocks2[j][i].pos]+=(computed.size()-p-1)-query(blocks2[j][i].c-1);
		}
		eh.clear();
		for(ll i=0;i<blocks1[j].size();++i)
		{
			eh.push_back(blocks1[j][i]);
		}
		sort(eh.begin(),eh.end());
		oh.clear();
		ll i1=0,i2=0;
		while(i1<eh.size()||i2<computed.size())
		{
			if(i1==eh.size())
			{
				oh.push_back(computed[i2]);
				++i2;
			}
			else if(i2==computed.size())
			{
				oh.push_back(eh[i1]);
				++i1;
			}
			else if(eh[i1]<computed[i2])
			{
				oh.push_back(eh[i1]);
				++i1;
			}
			else 
			{
				oh.push_back(computed[i2]);
				++i2;
			}
		}
		computed=oh;
		/*cout<<"computed:\n";
		for(ll j=0;j<computed.size();j++)
		{
			cout<<computed[j].a<<" "<<computed[j].b<<" "<<computed[j].c<<endl;
		}*/
	}
	for(ll i=1;i<=q;++i)
	{
		cout<<ans[i]<<"\n";
	}
return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:142:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(ll i1=0;i1<blocks2[j].size();++i1)
      |               ~~^~~~~~~~~~~~~~~~~~
examination.cpp:144:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    for(ll i2=0;i2<blocks1[j].size();++i2)
      |                ~~^~~~~~~~~~~~~~~~~~
examination.cpp:154:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(ll i=0;i<blocks2[j].size();++i)
      |              ~^~~~~~~~~~~~~~~~~~
examination.cpp:164:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   for(ll i=0;i<blocks1[j].size();++i)
      |              ~^~~~~~~~~~~~~~~~~~
examination.cpp:171:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   while(i1<eh.size()||i2<computed.size())
      |         ~~^~~~~~~~~~
examination.cpp:171:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   while(i1<eh.size()||i2<computed.size())
      |                       ~~^~~~~~~~~~~~~~~~
examination.cpp:173:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |    if(i1==eh.size())
      |       ~~^~~~~~~~~~~
examination.cpp:178:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |    else if(i2==computed.size())
      |            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57