#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=2e5+5,mod=30013;
int n;
vector<pair<pair<int,int>,pair<int,int> > > t;
unsigned short add(unsigned short a,unsigned short b)
{
a+=b;
if(a>=mod)
a-=mod;
return a;
}
pair<int,unsigned short> merge(pair<int,unsigned short> a,pair<int,unsigned short> b)
{
pair<int,unsigned short> sol={max(a.f,b.f),0};
if(a.f==sol.f)
sol.s=add(sol.s,a.s);
if(b.f==sol.f)
sol.s=add(sol.s,b.s);
return sol;
}
struct node{
pair<int,unsigned short> maxx;
int l,r;
};
vector<node> drvo;
int newNode()
{
node a;
a.l=a.r=-1;
drvo.pb(a);
return drvo.size()-1;
}
int copyNode(int i)
{
drvo.pb(drvo[i]);
return drvo.size()-1;
}
vector<int> roots(N);
void build(int l=0,int r=N-1,int i=0)
{
if(l==r)
{
if(l==N-1)
drvo[i].maxx={0,1};
return;
}
int a=newNode(),m=(l+r)>>1;
drvo[i].l=a;
build(l,m,a);
a=newNode();
drvo[i].r=a;
build(m+1,r,a);
drvo[i].maxx=merge(drvo[drvo[i].l].maxx,drvo[drvo[i].r].maxx);
}
int sett(int pos,pair<int,int> a,int i,int l=0,int r=N-1)
{
if(l>pos||r<pos)
return i;
int tr=copyNode(i);
if(l==r)
{
drvo[tr].maxx=merge(drvo[tr].maxx,a);
return tr;
}
int m=(l+r)>>1;
int aa=sett(pos,a,drvo[tr].l,l,m);
drvo[tr].l=aa;
aa=sett(pos,a,drvo[tr].r,m+1,r);
drvo[tr].r=aa;
drvo[tr].maxx=merge(drvo[drvo[tr].l].maxx,drvo[drvo[tr].r].maxx);
return tr;
}
pair<int,int> get(int qs,int i,int qe=N-1,int l=0,int r=N-1)
{
if(qs>r||qe<l)
return {0,0};
if(qs<=l&&qe>=r)
return drvo[i].maxx;
int m=(l+r)>>1;
return merge(get(qs,drvo[i].l,qe,l,m),get(qs,drvo[i].r,qe,m+1,r));
}
int getRoot(int i)
{
int l=i+1,r=n-1;
while(l<r)
{
int m=(l+r)>>1;
if(t[m].f.f>t[i].f.s)
r=m;
else
l=m+1;
}
if(t[r].f.f<=t[i].f.s)
return 0;
return roots[r];
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%i",&n);
t.resize(n);
newNode();
build();
vector<int> y;
for(int i=0;i<n;i++)
scanf("%i %i %i %i",&t[i].f.f,&t[i].f.s,&t[i].s.f,&t[i].s.s),y.pb(t[i].s.f),y.pb(t[i].s.s);
sort(all(y));
y.erase(unique(all(y)),y.end());
map<int,int> mapa;
for(int i=0;i<(int)y.size();i++)
mapa[y[i]]=i;
for(auto &p:t)
p.s.f=mapa[p.s.f],p.s.s=mapa[p.s.s];
mapa.clear();
sort(all(t));
pair<int,int> sol={0,0};
for(int ind=n-1;ind>=0;ind--)
{
int root=getRoot(ind);
auto val=get(t[ind].s.s+1,root);
val.f++;
roots[ind]=sett(t[ind].s.f,val,roots[ind+1]);
sol=merge(sol,val);
}
printf("%i %i\n",sol.f,sol.s);
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
trapezoid.cpp:131:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i %i",&t[i].f.f,&t[i].f.s,&t[i].s.f,&t[i].s.s),y.pb(t[i].s.f),y.pb(t[i].s.s);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
9440 KB |
Output is correct |
| 2 |
Correct |
19 ms |
9440 KB |
Output is correct |
| 3 |
Correct |
22 ms |
9440 KB |
Output is correct |
| 4 |
Correct |
20 ms |
9440 KB |
Output is correct |
| 5 |
Correct |
23 ms |
9568 KB |
Output is correct |
| 6 |
Correct |
25 ms |
9568 KB |
Output is correct |
| 7 |
Correct |
27 ms |
9440 KB |
Output is correct |
| 8 |
Correct |
31 ms |
9572 KB |
Output is correct |
| 9 |
Correct |
52 ms |
18772 KB |
Output is correct |
| 10 |
Correct |
77 ms |
19900 KB |
Output is correct |
| 11 |
Correct |
94 ms |
20536 KB |
Output is correct |
| 12 |
Correct |
193 ms |
39844 KB |
Output is correct |
| 13 |
Correct |
227 ms |
41076 KB |
Output is correct |
| 14 |
Correct |
260 ms |
42312 KB |
Output is correct |
| 15 |
Correct |
302 ms |
42792 KB |
Output is correct |
| 16 |
Correct |
329 ms |
43292 KB |
Output is correct |
| 17 |
Correct |
327 ms |
43968 KB |
Output is correct |
| 18 |
Correct |
298 ms |
44480 KB |
Output is correct |
| 19 |
Runtime error |
354 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
387 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
