Submission #1008942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008942		doducanh	trapezoid (balkan11_trapezoid)	C++14	100 / 100	70 ms	8416 KiB

trapezoid

#include <bits/stdc++.h>
 
using namespace std;
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=2e9;
pair<int,int> cmax(pair<int,int>a,pair<int,int>b)
{
    if(a.fi<b.fi)a=b;
    else{
        if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
    }
    return a;
}
int id(int x,vector<pair<int,int>> &tmp)
{
    return lower_bound(tmp.begin(),tmp.end(),make_pair(x,-maxx))-tmp.begin()+1;
}
struct BIT
{
    int n;
    vector<pair<int,int>>t;
    BIT(){}
    BIT(int n):n(n),t(n+7){}
    void up(int x,pair<int,int> val){
        for(;x<n;x+=(x&(-x)))t[x]=cmax(t[x],val);
    }
    pair<int,int>get(int x)
    {
        if(x<=0)return {0,1};
        pair<int,int>res={0,1};
        for(;x;x-=(x&(-x)))res=cmax(res,t[x]);
        return res;
    }
};
int a[maxn],b[maxn],c[maxn],d[maxn];
int n;
pair<int,int>ans[maxn];
vector<pair<int,int>>top;
vector<pair<int,int>>bot;
main()
{
//    freopen("trapezoid.in","r",stdin);
//    freopen("trapezoid.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        top.push_back({a[i],i});
        top.push_back({b[i],i});
        bot.push_back({c[i],i});
        bot.push_back({d[i],i});
    }
    sort(top.begin(),top.end());
    sort(bot.begin(),bot.end());
    BIT t(bot.size()+7);
    for(pair<int,int>p:top){
        int x=p.fi;
        int i=p.se;
        if(x==a[i]){
            int x=id(c[i],bot)-1;
            pair<int,int>tmp=t.get(x);
            ans[i]={tmp.fi+1,tmp.se};
        }
        else if(x==b[i]){
            int x=id(d[i],bot);
            t.up(x,ans[i]);
        }
    }
    pair<int,int>res={0,0};
    for(int i=1;i<=n;i++){
        res=cmax(res,ans[i]);
    }
    cout<<res.fi<<" "<<res.se;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~

• Subtask 1: 100 / 100