# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924621 | Warinchai | trapezoid (balkan11_trapezoid) | C++14 | 139 ms | 42520 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int md=30013;
int sec=0;
struct trap{
int a,b,c,d;
int id;
trap(int w=0,int x=0,int y=0,int z=0,int i=0){
a=w,b=x,c=y,d=z;
id=i;
}
bool operator<(const trap &x){
if(sec==0)return a<x.a;
return b<x.b;
}
};
struct segtree{
struct node{
int val,cnt;
node(int v=0,int cn=0){
val=v,cnt=cn;
}
friend node operator+(node a,node b){
node c;
c.val=max(a.val,b.val);
c.cnt=(a.val==b.val?a.cnt+b.cnt:(a.val>b.val?a.cnt:b.cnt))%md;
return c;
}
};
node info[1600005];
void upd(int st,int en,int i,int pos,int val,int cnt){
if(st>pos||en<pos)return;
if(st==en)return void(info[i]=node(val,cnt));
int m=(st+en)/2;
upd(st,m,i*2,pos,val,cnt);
upd(m+1,en,i*2+1,pos,val,cnt);
info[i]=info[i*2]+info[i*2+1];
}
node fans(int st,int en,int i,int l,int r){
if(st>r||en<l)return node();
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}tr;
queue<pair<pair<int,int>,pair<int,int> >>q;
vector<trap>vb;
vector<trap>v;
vector<int>ord;
int num[100005][2];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=0;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
v.push_back(trap(a,b,c,d,i));
vb.push_back(trap(a,b,c,d,i));
ord.push_back(a);
ord.push_back(b);
ord.push_back(c);
ord.push_back(d);
}
sort(ord.begin(),ord.end());
sort(v.begin(),v.end());
sec=1;
sort(vb.begin(),vb.end());
int cur=0;
for(int i=0;i<v.size();i++){
while(cur<n&&vb[cur].b<v[i].a){
int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1;
tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]);
cur++;
}
int pos=lower_bound(ord.begin(),ord.end(),v[i].c-1)-ord.begin()+1;
auto temp=tr.fans(1,4*n,1,1,pos);
num[v[i].id][0]=temp.val+1;
num[v[i].id][1]=temp.val==0?1:temp.cnt;
//cerr<<v[i].id<<" "<<num[v[i].id][0]<<" "<<num[v[i].id][1]<<"\n";
}
while(cur<n){
int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1;
tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]);
cur++;
}
cout<<tr.info[1].val<<" "<<tr.info[1].cnt;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |