Submission #126767

#	Time	Username	Problem	Language	Result	Execution time	Memory
126767		TadijaSebez	Examination (JOI19_examination)	C++11	100 / 100	634 ms	25472 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
struct BIT2D
{
	vector<int> all[N],sum[N];
	BIT2D(){}
	void Ins(int x, int y){ for(int i=x;i;i-=i&-i) if(all[i].empty() || all[i].back()!=y) all[i].pb(y);}
	void Build(){ for(int i=1;i<N;i++) sum[i].resize(all[i].size());}
	int Pos(int x, int y){ return lower_bound(all[x].begin(),all[x].end(),y)-all[x].begin()+1;}
	void Set(int x, int y){ for(int i=x;i;i-=i&-i) for(int j=Pos(i,y);j;j-=j&-j) sum[i][j-1]++;}
	int Get(int x, int y){ int ans=0;for(int i=x;i<N;i+=i&-i) for(int j=Pos(i,y);j<=all[i].size();j+=j&-j) ans+=sum[i][j-1];return ans;}
} ST;
int qid[N],id[N],s[N],t[N],a[N],b[N],c[N],ans[N];
vector<int> cp;
int Pos(int x){ return lower_bound(cp.begin(),cp.end(),x)-cp.begin()+1;}
int main()
{
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++) scanf("%i %i",&s[i],&t[i]),id[i]=i,cp.pb(s[i]);
	sort(cp.begin(),cp.end());cp.resize(unique(cp.begin(),cp.end())-cp.begin());
	sort(id+1,id+1+n,[&](int i, int j){ return t[i]<t[j];});
	for(int i=1;i<=n;i++) ST.Ins(Pos(s[id[i]]),t[id[i]]);ST.Build();
	sort(id+1,id+1+n,[&](int i, int j){ return s[i]+t[i]>s[j]+t[j];});
	for(int i=1;i<=q;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),qid[i]=i;
	sort(qid+1,qid+1+q,[&](int i, int j){ return c[i]>c[j];});
	for(int i=1,j=1;i<=q;i++)
	{
		for(;j<=n && s[id[j]]+t[id[j]]>=c[qid[i]];j++) ST.Set(Pos(s[id[j]]),t[id[j]]);
        ans[qid[i]]=ST.Get(Pos(a[qid[i]]),b[qid[i]]);
	}
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'int BIT2D::Get(int, int)':
examination.cpp:13:80: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int Get(int x, int y){ int ans=0;for(int i=x;i<N;i+=i&-i) for(int j=Pos(i,y);j<=all[i].size();j+=j&-j) ans+=sum[i][j-1];return ans;}
                                                                               ~^~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:25:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=n;i++) ST.Ins(Pos(s[id[i]]),t[id[i]]);ST.Build();
  ^~~
examination.cpp:25:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=n;i++) ST.Ins(Pos(s[id[i]]),t[id[i]]);ST.Build();
                                                       ^~
examination.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:22:58: 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",&s[i],&t[i]),id[i]=i,cp.pb(s[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
examination.cpp:27:59: 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 %i",&a[i],&b[i],&c[i]),qid[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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