Submission #1017474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017474		dosts	trapezoid (balkan11_trapezoid)	C++17	0 / 100	138 ms	39872 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 TRAP {
    int a,b,c,d;
};

vi v;

int idx(int x){
    return upper_bound(all(v),x)-v.begin();
}

struct MFT {
    int n;
    vi bit;

    MFT(int nn) {
        n = nn;
        bit.assign(n+1,0);
    }

    void put(int p,int v) {
        for (int i=p;i<=n;i+=i&-i) bit[i] = max(bit[i],v);
    }
    int get(int p) {
        int ans = 0;
        for (int i=p;i>0;i-=i&-i) ans = max(ans,bit[i]);
        return ans;
    }
};

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


struct SFT {
    int n;
    vi bit;

    SFT(int nn) {
        n = nn;
        bit.assign(n+1,0);
    }

    void put(int p,int v) {
        for (int i=p;i<=n;i+=i&-i) bit[i] = add(bit[i],v);
    }
    void set(int p,int v) {
        for (int i=p;i<=n;i+=i&-i) bit[i] = v;
    }
    int get(int p) {
        int ans = 0;
        for (int i=p;i>0;i-=i&-i) ans = add(ans,bit[i]);
        return ans;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<TRAP> trap(n+1);
    for (int i=1;i<=n;i++) cin >> trap[i].a >> trap[i].b >> trap[i].c >> trap[i].d;
    for (int i=1;i<=n;i++) {
        v.push_back(trap[i].a);
        v.push_back(trap[i].b);
        v.push_back(trap[i].c);
        v.push_back(trap[i].d);
    }
    sort(v.begin(),v.end());
    v.erase(unique(all(v)),v.end());
    for (int i=1;i<=n;i++) {
        trap[i].a = idx(trap[i].a);
        trap[i].b = idx(trap[i].b);
        trap[i].c = idx(trap[i].c);
        trap[i].d = idx(trap[i].d);
    }
    int sz = v.size();
    MFT mft(sz);
    vi dp(n+1,0);
    vi in[sz+1],out[sz+1];
    for (int i=1;i<=n;i++) in[trap[i].a].push_back(i);
    for (int i=1;i<=n;i++) out[trap[i].b].push_back(i);
    for (int i=1;i<=sz;i++) {
        for (auto it : in[i]) dp[it] = mft.get(trap[it].c)+1;
        for (auto it : out[i]) mft.put(trap[it].d,dp[it]);
    }
    int mx = *max_element(dp.begin()+1,dp.end());

    vi x[n+1];
    for (int i=1;i<=n;i++) x[dp[i]].push_back(i);
    vi ways(n+1,0);
    for (auto it : x[1]) ways[it] = add(ways[it],1);
    SFT sft(sz);
    for (int i=2;i<=n;i++) {
        vector<pii> vv;
        for (auto it : x[i-1]) vv.push_back({trap[it].b,it});
        for (auto it : x[i]) vv.push_back({trap[it].a,it});
        sort(vv.begin(),vv.end());
        for (auto it : vv) {
            if (dp[it.ss] == i) ways[it.ss] = add(ways[it.ss],sft.get(trap[it.ss].c));
            else sft.put(trap[it.ss].d,ways[it.ss]);
        }
        for (auto it : vv) sft.set(trap[it.ss].d,0);
    }
    int ans = 0;
    for (int i=1;i<=n;i++) if (dp[i] == mx) ans = add(ans,ways[i]);
    cout << ans << '\n';
    //SERIFEFEDARTAR ORZ
}  
 
                
                            
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);
/*     #else 
        freopen("lazy.in","r",stdin);
        freopen("lazy.out","w",stdout); */
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 0 / 100