oj.uz

Submission #340991

# Submission time Handle Problem Language Result Execution time Memory
340991 2020-12-28T20:53:45 Z ogibogi2004 Examination (JOI19_examination) C++14
0 / 100
 1321 ms 31532 KB 
//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int SQRT=400;
int n,q;
int ans[MAXN];
set<int>xs,ys,zs;
int s[MAXN],t[MAXN],sum[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
map<int,int>newx,newy,newz;
struct student
{
	int a,b,c;
	student(){}
	student(int _a,int _b,int _c)
	{
		a=_a;b=_b;c=_c;
	}
	bool operator<(student const& other)const
	{
		return b<other.b;
	}
};
struct query
{
	int a,b,c,pos;
	query(){}
	query(int _a,int _b,int _c,int _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];
int BIT[MAXN];
void update(int idx,int val)
{
	++idx;
	for(;idx<MAXN;idx+=idx&(-idx))
	{
		BIT[idx]+=val;
	}
}
int query(int idx)
{
	++idx;
	int 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(int i=1;i<=n;++i)
	{
		cin>>s[i]>>t[i];
		sum[i]=s[i]+t[i];
		xs.insert(s[i]);ys.insert(t[i]);zs.insert(sum[i]);
	}
	int 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(int i=1;i<=n;++i)
	{
		s[i]=newx[s[i]];
		t[i]=newy[t[i]];
		sum[i]=newz[sum[i]];
	}
	for(int i=1;i<=q;++i)
	{
		cin>>x[i]>>y[i]>>z[i];
		auto it=xs.lower_bound(x[i]);
		if(it==xs.end())x[i]=cntx+1;
		else x[i]=newx[(*it)];
		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)];
	}
	//cout<<"students:\n";
	for(int 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(int 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(int 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(int 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(int 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(int i1=0;i1<blocks2[j].size();++i1)
		{
			for(int 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());
		int p=computed.size()-1;
		for(int 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(int i=0;i<blocks1[j].size();++i)
		{
			eh.push_back(blocks1[j][i]);
		}
		sort(eh.begin(),eh.end());
		oh.clear();
		int 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(int j=0;j<computed.size();j++)
		{
			cout<<computed[j].a<<" "<<computed[j].b<<" "<<computed[j].c<<endl;
		}*/
	}
	for(int i=1;i<=q;++i)
	{
		cout<<ans[i]<<"\n";
	}
return 0;
}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Incorrect 17 ms 2028 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1321 ms 31532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1321 ms 31532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Incorrect 17 ms 2028 KB Output isn't correct
8 Halted 0 ms 0 KB -