#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>
if(ql>qr) return mkp( 0 , 0 );
int cl = st[cidx].sl;
int cr = st[cidx].sr;
if( qr<cl or cr<ql ){
return mkp( 0 , 0 );
}
if( ql<=cl and cr<=qr ){
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);
//
//freopen("Text.txt","r",stdin);
//
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;
}
//int ST = clock();
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';
//int ED = clock();
//int DT = ED - ST;
//cerr<<"n = "<<n<<" : T = "<<DT<<" ms"<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
620 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1732 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1644 KB |
Output is correct |
| 8 |
Correct |
15 ms |
2540 KB |
Output is correct |
| 9 |
Correct |
34 ms |
4912 KB |
Output is correct |
| 10 |
Correct |
54 ms |
8172 KB |
Output is correct |
| 11 |
Correct |
88 ms |
10860 KB |
Output is correct |
| 12 |
Correct |
193 ms |
21352 KB |
Output is correct |
| 13 |
Correct |
283 ms |
23396 KB |
Output is correct |
| 14 |
Correct |
293 ms |
36196 KB |
Output is correct |
| 15 |
Correct |
310 ms |
34792 KB |
Output is correct |
| 16 |
Correct |
364 ms |
35684 KB |
Output is correct |
| 17 |
Correct |
369 ms |
40868 KB |
Output is correct |
| 18 |
Correct |
271 ms |
32740 KB |
Output is correct |
| 19 |
Correct |
377 ms |
42468 KB |
Output is correct |
| 20 |
Correct |
418 ms |
42852 KB |
Output is correct |
