제출 #1016995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016995		dosts	사다리꼴 (balkan11_trapezoid)	C++17	12 / 100	130 ms	30404 KiB

trapezoid

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int N = 1e6+1,inf = 2e9,B = 23,MOD = 30013,LIM = 1e9;    
 
struct T {
    int a,b,c,d;
};


int add(int x,int y){
    return ((x+y) >= MOD ? x+y-MOD : x+y);
}


struct ST {
    vi t;

    ST(int nn) {
        t.assign(4*nn+1,0);
    }

    int query(int node,int l,int r,int L,int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = max(t[node],v);
            return;
        }
        int m = (l+r) >> 1;
        if (p<=m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = max(t[2*node],t[2*node+1]);
    }
};

void solve() {
    int n;
    cin >> n;
    T traps[n+1];
    for (int i=1;i<=n;i++) cin >> traps[i].a >> traps[i].b >> traps[i].c >> traps[i].d;
    vi v;
    for (int i=1;i<=n;i++) {
        v.push_back(traps[i].a);
        v.push_back(traps[i].b);
        v.push_back(traps[i].c);
        v.push_back(traps[i].d);
    }
    sort(v.begin(),v.end());
    v.erase(unique(all(v)),v.end());
    for (int i=1;i<=n;i++) {
        traps[i].a = upper_bound(all(v),traps[i].a)-v.begin();
        traps[i].b = upper_bound(all(v),traps[i].b)-v.begin();
        traps[i].c = upper_bound(all(v),traps[i].c)-v.begin();
        traps[i].d = upper_bound(all(v),traps[i].d)-v.begin();
    }
    sort(traps+1,traps+n+1,[&](const T& t1,const T& t2) {
        return t1.a < t2.a;
    });;
    int sz = v.size();
    vector<pii> dp(n+1);
    ST st(sz);
    set<pii> fat_arrays[n+1];
    for (int i=n;i>=1;i--) {
        //cout << "TRAP" sp traps[i].a sp traps[i].b sp traps[i].c sp traps[i].d << endl;
        int mn = max(traps[i].b,traps[i].d)+1;
        //mn..lim de en iyi dp valuesu
        dp[i].first = st.query(1,1,sz,mn,sz)+1;
        int cont = 0;
        auto it = fat_arrays[dp[i].ff-1].lower_bound({mn,-inf});
        if (fat_arrays[dp[i].ff-1].empty() || it == fat_arrays[dp[i].ff-1].begin()) cont = 0;
        else {
            --it;
            cont = it->second;
        }
        dp[i].second = cont;
        if (dp[i].first == 1) dp[i].second = add(dp[i].second,1);
        fat_arrays[dp[i].first].insert({i,dp[i].second});
        st.update(1,1,sz,traps[i].c,dp[i].first);
        //cout << dp[i].ff sp dp[i].ss << endl;
    };
    int mx = 0;
    for (int i=1;i<=n;i++) mx = max(mx,dp[i].ff);
    int sm = 0;
    for (int i=1;i<=n;i++) if (dp[i].ff == mx) sm = add(sm,dp[i].ss);
    cout << mx sp sm << '\n';
}  
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 12 / 100