oj.uz

Submission #340996

# Submission time Handle Problem Language Result Execution time Memory
340996 2020-12-28T20:56:34 Z ogibogi2004 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 30060 KB 
//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int SQRT=3002;
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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 62 ms 2156 KB Output is correct
8 Correct 60 ms 2156 KB Output is correct
9 Correct 62 ms 2284 KB Output is correct
10 Correct 63 ms 1772 KB Output is correct
11 Correct 62 ms 1772 KB Output is correct
12 Correct 55 ms 1260 KB Output is correct
13 Correct 57 ms 2156 KB Output is correct
14 Correct 58 ms 2156 KB Output is correct
15 Correct 58 ms 2284 KB Output is correct
16 Correct 31 ms 1772 KB Output is correct
17 Correct 47 ms 1772 KB Output is correct
18 Correct 12 ms 1260 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 30060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 30060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 62 ms 2156 KB Output is correct
8 Correct 60 ms 2156 KB Output is correct
9 Correct 62 ms 2284 KB Output is correct
10 Correct 63 ms 1772 KB Output is correct
11 Correct 62 ms 1772 KB Output is correct
12 Correct 55 ms 1260 KB Output is correct
13 Correct 57 ms 2156 KB Output is correct
14 Correct 58 ms 2156 KB Output is correct
15 Correct 58 ms 2284 KB Output is correct
16 Correct 31 ms 1772 KB Output is correct
17 Correct 47 ms 1772 KB Output is correct
18 Correct 12 ms 1260 KB Output is correct
19 Execution timed out 3090 ms 30060 KB Time limit exceeded
20 Halted 0 ms 0 KB -