#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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
