제출 #1288361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288361		LmaoLmao	사다리꼴 (balkan11_trapezoid)	C++20	25 / 100	95 ms	29248 KiB

trapezoid

#include <bits/stdc++.h>
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,long long>;
using aa = array<int,4>;
using ll = long long;
const int N=1e5+5;
const int MOD=30013;

struct BIT {
    int F[N];
    void update(int pos,int val) {
        for(int i=pos;i<N;i+=i & -i) {
            F[i]=max(F[i],val);
        }
    }
    int get(int pos) {
        int res=0;
        for(int i=pos;i>0;i-=i & -i) {
            res=max(res,F[i]);
        }
        return res;
    }
} Fmax;

struct BIThuytranbebde {
    vector<int> F;
    vector<int> nen;
    void update(int pos,int val) {
        int x=lower_bound(nen.begin(),nen.end(),pos)-nen.begin();
        for(int i=x;i<F.size();i+=i & -i) {
            F[i]+=val;
            F[i]%=MOD;
        }
    }
    int get(int pos) {
        int res=0;
        int x=lower_bound(nen.begin(),nen.end(),pos)-nen.begin();
        x--;
        for(int i=x;i>0;i-=i & -i) {
            res+=F[i];
            res%=MOD;
        }
        return res;
    }
} Fsum[N*4];


aa a[N];
vector<int> nen;
vector<ii> qr[N*4];
int dp[N];
int cnt[N];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<4;j++) {
            cin >> a[i][j];
            nen.push_back(a[i][j]);
        }
    }
    sort(nen.begin(),nen.end());
    for(int i=1;i<=n;i++) {
        for(int j=0;j<4;j++) {
            a[i][j]=lower_bound(nen.begin(),nen.end(),a[i][j])-nen.begin()+1;
        }
        qr[a[i][0]].push_back({0,i});
        qr[a[i][1]].push_back({1,i});
    }
    cnt[0]=1;
    Fsum[0].F.push_back(0);
    Fsum[0].F.push_back(1);
    Fsum[0].nen.push_back(0);
    Fsum[0].nen.push_back(0);
    int ans=0;
    for(int i=1;i<=nen.size();i++) {
        Fsum[i].F.push_back(0);
        Fsum[i].nen.push_back(0);
        for(ii x:qr[i]) {
            if(!x.fi) {
                dp[x.se]=Fmax.get(a[x.se][2])+1;
                Fsum[dp[x.se]].F.push_back(0);
                Fsum[dp[x.se]].nen.push_back(a[x.se][3]);
                //Fsum[dp[x.se]-1].F.push_back(0);
                //Fsum[dp[x.se]-1].nen.push_back(i);
                ans=max(ans,dp[x.se]);
                //cout << nen[a[x.se][2]-1] << ' ' << 1 << ' ' << x.se << endl;
            }
            else {
                Fmax.update(a[x.se][3],dp[x.se]);
                //cout << nen[a[x.se][3]-1] << ' ' << 2 << ' ' << x.se <<  endl;;
            }
        }
        sort(Fsum[i].nen.begin(),Fsum[i].nen.end());
    }
    for(int i=1;i<=nen.size();i++) {
        for(ii x:qr[i]) {
            if(!x.fi) {
                cnt[x.se]=Fsum[dp[x.se]-1].get(a[x.se][2]);
                //cout << nen[a[x.se][2]-1] << ' ' << 1 << ' ' << x.se << endl;
            }
            else {
                Fsum[dp[x.se]].update(a[x.se][3],cnt[x.se]);
                //cout << nen[a[x.se][3]-1] << ' ' << 2 << ' ' << x.se <<  endl;;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) {
        //cout << dp[i] << ' ' << cnt[i] << endl;
        res+=(dp[i]==ans)*cnt[i];
        res%=MOD;
    }
    //cout << Fsum[1].F[0] << endl;
    //cout << lower_bound(Fsum[1].nen.begin(),Fsum[1].nen.end(),16)-Fsum[1].nen.begin() << endl;
    cout << ans << ' ' << res;
    return 0;
}

• Subtask 1: 25 / 100