답안 #145861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145861 2019-08-21T07:34:31 Z TadijaSebez 사다리꼴 (balkan11_trapezoid) C++11
100 / 100
256 ms 26464 KB
#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

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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 12 ms 9976 KB Output is correct
5 Correct 14 ms 10104 KB Output is correct
6 Correct 16 ms 10332 KB Output is correct
7 Correct 17 ms 10360 KB Output is correct
8 Correct 20 ms 10616 KB Output is correct
9 Correct 30 ms 11512 KB Output is correct
10 Correct 48 ms 13160 KB Output is correct
11 Correct 60 ms 13812 KB Output is correct
12 Correct 119 ms 18284 KB Output is correct
13 Correct 146 ms 19948 KB Output is correct
14 Correct 178 ms 21608 KB Output is correct
15 Correct 202 ms 22628 KB Output is correct
16 Correct 220 ms 23352 KB Output is correct
17 Correct 224 ms 24260 KB Output is correct
18 Correct 196 ms 24928 KB Output is correct
19 Correct 222 ms 25284 KB Output is correct
20 Correct 256 ms 26464 KB Output is correct