Submission #145861

#	Time	Username	Problem	Language	Result	Execution time	Memory
145861		TadijaSebez	trapezoid (balkan11_trapezoid)	C++11	100 / 100	256 ms	26464 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int M=2*N;
const int H=2*M;
const int mod=30013;
int ls[H],rs[H],tsz,root;
pair<int,int> mx[H];
pair<int,int> operator + (pair<int,int> a, pair<int,int> b)
{
	if(a.first!=b.first) return a.first<b.first?b:a;
	return {a.first,(a.second+b.second)%mod};
}
void Set(int &c, int ss, int se, int qi, pair<int,int> x)
{
	if(!c) c=++tsz;
	if(ss==se){ mx[c]=x;return;}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,x);
	else Set(rs[c],mid+1,se,qi,x);
	mx[c]=mx[ls[c]]+mx[rs[c]];
}
pair<int,int> Get(int c, int ss, int se, int qs, int qe)
{
	if(qs<=ss && qe>=se) return mx[c];
	int mid=ss+se>>1;
	if(qe<=mid) return Get(ls[c],ss,mid,qs,qe);
	if(qs>mid) return Get(rs[c],mid+1,se,qs,qe);
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
vector<int> id1,id2;
int l1[N],r1[N],l2[N],r2[N];
pair<int,int> dp[N];
vector<int> Qs[M],Us[M];
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i %i %i",&l1[i],&r1[i],&l2[i],&r2[i]);
		id1.pb(l1[i]);id1.pb(r1[i]);
		id2.pb(l2[i]);id2.pb(r2[i]);
	}
	sort(id1.begin(),id1.end());
	id1.resize(unique(id1.begin(),id1.end())-id1.begin());
	sort(id2.begin(),id2.end());
	id2.resize(unique(id2.begin(),id2.end())-id2.begin());
	for(int i=1;i<=n;i++)
	{
		l1[i]=lower_bound(id1.begin(),id1.end(),l1[i])-id1.begin()+1;
		r1[i]=lower_bound(id1.begin(),id1.end(),r1[i])-id1.begin()+1;
		l2[i]=lower_bound(id2.begin(),id2.end(),l2[i])-id2.begin()+1;
		r2[i]=lower_bound(id2.begin(),id2.end(),r2[i])-id2.begin()+1;
		Qs[l1[i]].pb(i);
		Us[r1[i]].pb(i);
	}
	int sz=id2.size();
	Set(root,0,sz,0,{0,1});
	for(int j=1;j<=id1.size();j++)
	{
		for(int i:Qs[j])
		{
			dp[i]=Get(root,0,sz,0,l2[i]-1);
			dp[i].first++;
		}
		for(int i:Us[j])
		{
			Set(root,0,sz,r2[i],dp[i]);
		}
	}
	pair<int,int> ans={0,0};
	for(int i=1;i<=n;i++) ans=ans+dp[i];
	printf("%i %i\n",ans.first,ans.second);
	return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void Set(int&, int, int, int, std::pair<int, int>)':
trapezoid.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
trapezoid.cpp: In function 'std::pair<int, int> Get(int, int, int, int, int)':
trapezoid.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=1;j<=id1.size();j++)
              ~^~~~~~~~~~~~
trapezoid.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
trapezoid.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i %i",&l1[i],&r1[i],&l2[i],&r2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100