Submission #204090

#	Time	Username	Problem	Language	Result	Execution time	Memory
204090		balbit	Port Facility (JOI17_port_facility)	C++14	0 / 100	89 ms	95612 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define SZ(x) x.size()
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<" : ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT

const int mod = 1e9+7;

const int maxn = 2e6+10;


struct BIT{
    vector<ll> s;
    int MX=0;
    ll QU(int e){
        ll re = 0; e ++;
        while (e>0) {
            re+=s[e]; re%=mod; e-=e&(-e);
        }return re;
    }
    ll QU(int l, int r){
        return QU(r)-QU(l-1);
    }
    void MO(int e, ll v){
        e++; while (e<MX){
            s[e]+=v;
            s[e] %= mod;
            e+=e&(-e);
        }
    }
    BIT(int _mx){
        MX = _mx; s.resize(MX+1);
    }
};

int lb[maxn], rb[maxn];
ll dp[maxn];
BIT rpt(maxn), lpt(maxn), DP(maxn);

bool compat(int x, int at, bool lst){ // x is last
    if (x==0) return 1;
    if (rb[at] > rb[x] && rb[x] > lb[at]) return 0; // Directly not ok
    int L = lpt.QU(lb[x-1],rb[x-1]) - (lst&&lb[x]<rb[x-1]);
    int R = rpt.QU(lb[x-1],rb[x-1]) - (lst&&rb[x]<rb[x-1]);
    if (L == R) {
        return 1;
    }else{
        return 0;
    }
}

signed main(){
    IOS();
    int n; cin>>n;
    if (n>5) assert(0);
    vector<pii> inp(n);
    for (int i = 0; i<n; i++){
        cin>>inp[i].f>>inp[i].s;
    }
    inp.pb({-1,2*n+2});
    inp.pb({-2,2*n+1});
    sort(ALL(inp));
    n+=2;
    for (int i = 0; i<n; i++){
        tie(lb[i],rb[i]) = inp[i];
        lb[i] += 2; rb[i] += 2;
    }
    dp[0] = dp[1] = 1;

    int last = 1;
    lpt.MO(lb[last],1);
    rpt.MO(rb[last],1);
    for (int i = 2; i<n; i++){
        if (i>2) {
            // maintain last compatible for parent
            while (rpt.QU(lb[i-1],rb[i-1])>1) {
                rpt.MO(rb[last],-1);
                lpt.MO(lb[last],-1);
                DP.MO(rb[last+1],-dp[last+1]);
                last++;
            }
            bug(last);
        }
        if (compat(last,i,1)) {
            dp[i] += dp[last];
        }
        if (compat(last-1,i,0)) {
            dp[i] += dp[last-1];
        }
        bug(i,dp[i]);

        while (rpt.QU(lb[i],rb[i])>0) {
            rpt.MO(rb[last],-1);
            lpt.MO(lb[last],-1);
            DP.MO(rb[last+1],-dp[last+1]);
            last++;
        }
        bug(last);
        dp[i] += DP.QU(lb[i]-1) + DP.QU(rb[i]+1,maxn-1);
        dp[i] %= mod;
        bug("end",i,dp[i]);
        DP.MO(rb[i],dp[i]);
        lpt.MO(lb[i],1);
        rpt.MO(rb[i],1);
    }
    cout<<dp[n-1]<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22