Submission #1079885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079885		tquyetthang2k7	trapezoid (balkan11_trapezoid)	C++14	100 / 100	101 ms	15800 KiB

trapezoid

#include<bits/stdc++.h>
//#define int long long
#define ii pair < int , int >
#define fi first
#define se second
#define endl '\n'
#define all(x) x.begin() , x.end()
#define pb push_back
#define TASK "trapezoid"
const int Max = 2e5+10;
const int INF = 1e9;
const int LOG = 20;
const int Mod = 30013;
using namespace std;

ii mx( const ii & a , const ii & b ){

    ii res;
    if ( a.fi == b.fi )res = { a.fi , (a.se + b.se)%Mod };
    else if ( a.fi > b.fi )res = a;
    else res = b;
    return res;


}


struct SegmentTree{

    int n ;
    vector < ii > st;

    SegmentTree( int _n ){
        n = _n;

        st.assign( 4*Max , {0,0} );

    }

    void update( int id , int l , int r, int i , ii val ){

        if ( l > i || r < i )return ;
        if ( l == r ){

            st[id] = mx( st[id] , val );
            return;

        }
        int mid = (l+r)>>1;
        if ( i <=mid )update( 2*id , l, mid , i , val );
        else update( 2*id+1, mid + 1, r , i , val );

        st[id] = mx( st[2*id] , st[2*id+1] );

    }
    ii get( int id , int l , int r , int u , int v ){


        if ( l > v || r < u)return {0,0};
        if ( l >=u && r<=v )return st[id];
        int mid = (l+r) >> 1;
        return mx( get( 2*id , l , mid ,u , v ) , get( 2*id+1, mid +1 , r , u , v)  );

    }


};

struct ht{
    int a,b,c,d;

};
vector < ii > queries;
int n ;
vector < ht > a( Max+10 );
vector < int > nen;
ii kq[Max+10];


void solve(void){
    cin >> n;
    for(int i =1; i<=n; i++){
        int b,c,d,e;
        cin >> b >> c >> d >> e;
        a[i]= { b,c,d,e };
        nen.push_back( d );
        nen.push_back( e );
        queries.push_back( { b, i }  );
        queries.push_back( {c,-i} );
    }
    nen.push_back( 0 );
    SegmentTree st(n);
    sort( all(nen) );
    sort( all( queries ) );
    nen.resize( unique( all(nen) ) - nen.begin() );

    for(int i=1; i<=n; i++){

        a[i].c = lower_bound( all(nen) , a[i].c ) - nen.begin();
        a[i].d = lower_bound( all(nen) , a[i].d ) - nen.begin();

    }

    st.update( 1,0,Max , 0 , {0,1} );

    for( ii h : queries){

        if ( h.se < 0 ){
            h.se = -h.se;
            st.update( 1,0,Max , a[h.se].d , kq[h.se]  );
        }
        else{

            kq[ h.se ] = st.get( 1,0,Max, 0 , a[h.se].c-1 );
            kq[h.se].fi++;
//            cout << h.se << ' ' << a[h.se].c-1 <<  ' ' <<   kq[h.se].fi << ' ' << kq[h.se].se  << endl;
        }

    }
    ii ans=st.get( 1,0,Max , 0 , Max );
    cout << ans.fi << ' ' << ans.se ;
}

signed main(){

    ios_base::sync_with_stdio( false );
    cin.tie(0);cout.tie(0);
    if  ( fopen( TASK".in" , "r"  ) ){
        freopen( TASK".in" , "r", stdin  );
        freopen( TASK".out" , "w", stdout  );
    }
    int t = 1;
//    cin >> t;
    while( t-- ){

        solve();

    }


}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen( TASK".in" , "r", stdin  );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen( TASK".out" , "w", stdout  );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100