# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1079885 | tquyetthang2k7 | 사다리꼴 (balkan11_trapezoid) | C++14 | 101 ms | 15800 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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();
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |