Submission #367065

#	Time	Username	Problem	Language	Result	Execution time	Memory
367065		Haruto810198	trapezoid (balkan11_trapezoid)	C++17	40 / 100	1098 ms	65540 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF=2147483647;
//const int MOD=1000000007;
const int MOD=30013;
const int mod=998244353;
const double eps=1e-12;

int n;
pair<pii,pii> pos[100001];
int dp[100001],dpcnt[100001];

vector<pair<int,pii>> ev;
/// modify: time, 0, idx
/// query : time, 1, idx

/// segment tree

struct Node{
    int sl,sr;
    int Max,cnt;
};

Node st[1600004]; /// root=1

void build(int cidx,int cl,int cr){

    st[cidx].sl = cl;
    st[cidx].sr = cr;
    st[cidx].Max = 0;
    st[cidx].cnt = 0;

    if(cl<cr){
        int mid = (cl+cr)/2;
        build(cidx*2,cl,mid);
        build(cidx*2+1,mid+1,cr);
    }

}

void modify(int cidx,int midx,int mMax,int mcnt){ /// arr[midx] -> <Max,cnt>

    int cl = st[cidx].sl;
    int cr = st[cidx].sr;

    if( midx<cl or cr<midx ){
        return;
    }

    if(cl==cr){
        st[cidx].Max = mMax;
        st[cidx].cnt = mcnt;
    }
    else{

        modify(cidx*2,midx,mMax,mcnt);
        modify(cidx*2+1,midx,mMax,mcnt);

        if( st[cidx*2].Max > st[cidx*2+1].Max ){
            st[cidx].Max = st[cidx*2].Max;
            st[cidx].cnt = st[cidx*2].cnt;
        }
        else if( st[cidx*2].Max == st[cidx*2+1].Max ){
            st[cidx].Max = st[cidx*2].Max;
            st[cidx].cnt = (st[cidx*2].cnt + st[cidx*2+1].cnt) % MOD;
        }
        else{
            st[cidx].Max = st[cidx*2+1].Max;
            st[cidx].cnt = st[cidx*2+1].cnt;
        }

    }

}

pii query(int cidx,int ql,int qr){ /// return <Max,cnt>

    int cl = st[cidx].sl;
    int cr = st[cidx].sr;

    if( qr<cl or cr<ql ){
        return mkp( 0 , 0 );
    }

    if(cl==cr){
        return mkp( st[cidx].Max , st[cidx].cnt );
    }
    else{

        pii ansl = query(cidx*2,ql,qr);
        pii ansr = query(cidx*2+1,ql,qr);

        pii ans;

        if( ansl.F > ansr.F ){
            ans.F = ansl.F;
            ans.S = ansl.S;
        }
        else if( ansl.F == ansr.F ){
            ans.F = ansl.F;
            ans.S = (ansl.S + ansr.S) % MOD;
        }
        else{
            ans.F = ansr.F;
            ans.S = ansr.S;
        }

        return ans;

    }

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    FOR(i,0,n-1,1){
        cin >> pos[i].F.F >> pos[i].F.S >> pos[i].S.F >> pos[i].S.S;
    }
    sort(pos,pos+n);

    /// discretize

    vi sorted;
    map<int,int> discr;
    FOR(i,0,n-1,1){
        sorted.pb( pos[i].F.F );
        sorted.pb( pos[i].F.S );
        sorted.pb( pos[i].S.F );
        sorted.pb( pos[i].S.S );
    }

    sort(sorted.begin(),sorted.end());

    for(int i : sorted){
        if( discr.find(i) == discr.end() ){
            discr[i] = discr.size();
        }
    }

    FOR(i,0,n-1,1){
        pos[i].F.F = discr[pos[i].F.F];
        pos[i].F.S = discr[pos[i].F.S];
        pos[i].S.F = discr[pos[i].S.F];
        pos[i].S.S = discr[pos[i].S.S];
    }

    /*
    cerr<<endl;
    cerr<<"discretized : "<<endl;
    FOR(i,0,n-1,1){
        cerr << pos[i].F.F << " " << pos[i].F.S << " " << pos[i].S.F << " " << pos[i].S.S << endl;
    }
    cerr<<endl;
    */

    /// build ST
    build(1,0,4*n-1);

    /// events

    FOR(i,0,n-1,1){
        /// modify: time=ur, 0, i
        ev.eb( pos[i].F.S , mkp(0,i) );
        /// query : time=ul, 1, i
        ev.eb( pos[i].F.F , mkp(1,i) );
    }
    sort(ev.begin(),ev.end());

    /// process events

    for(auto E : ev){

        int Time = E.F;
        int type = E.S.F;
        int idx = E.S.S;

        //cerr<<"Time = "<<Time<<" idx = "<<idx<<"\t";

        if( type == 0 ){ /// modify
            modify( 1 , pos[idx].S.S , dp[idx] , dpcnt[idx] );
            //cerr<<"modify arr["<<pos[idx].S.S<<"] -> ("<<dp[idx]<<","<<dpcnt[idx]<<")"<<endl;
        }
        else{ /// query
            pii qans = query( 1 , 0 , pos[idx].S.F-1 );
            dp[idx] = qans.F + 1;
            if(dp[idx]>1) dpcnt[idx] = qans.S;
            else dpcnt[idx] = 1;
            //cerr<<"query ("<<0<<","<<pos[idx].S.F-1<<") = ("<<dp[idx]<<","<<dpcnt[idx]<<")"<<endl;
        }

        //cerr<<endl;

    }

    /*
    cerr<<"dp : ";
    FOR(i,0,n-1,1){
        cerr<<dp[i]<<" ";
    }
    cerr<<endl;

    cerr<<"dpcnt : ";
    FOR(i,0,n-1,1){
        cerr<<dpcnt[i]<<" ";
    }
    cerr<<endl;
    */

    int res_Max = 0;
    int res_cnt = 0;
    FOR(i,0,n-1,1){
        if( dp[i] > res_Max ){
            res_Max = dp[i];
            res_cnt = dpcnt[i];
        }
        else if( dp[i] == res_Max ){
            res_cnt += dpcnt[i];
            res_cnt %= MOD;
        }
    }

    cout<<res_Max<<" "<<res_cnt<<'\n';

    return 0;

}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:196:13: warning: unused variable 'Time' [-Wunused-variable]
  196 |         int Time = E.F;
      |             ^~~~

• Subtask 1: 40 / 100