# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1007685 | doducanh | 사다리꼴 (balkan11_trapezoid) | C++14 | 1090 ms | 8920 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=2e9;
pair<int,int> cmax(pair<int,int>a,pair<int,int>b)
{
if(a.fi<b.fi)a=b;
else{
if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
}
return a;
}
int id(int x,vector<pair<int,int>>tmp)
{
return lower_bound(tmp.begin(),tmp.end(),make_pair(x,-maxx))-tmp.begin()+1;
}
struct BIT
{
int n;
vector<pair<int,int>>t;
BIT(){}
BIT(int n):n(n),t(n+7){}
void up(int x,pair<int,int> val){
for(;x<n;x+=(x&(-x)))t[x]=cmax(t[x],val);
}
pair<int,int>get(int x)
{
if(x<=0)return {0,1};
pair<int,int>res={0,1};
for(;x;x-=(x&(-x)))res=cmax(res,t[x]);
return res;
}
};
int a[maxn],b[maxn],c[maxn],d[maxn];
int n;
pair<int,int>ans[maxn];
vector<pair<int,int>>top;
vector<pair<int,int>>bot;
main()
{
// freopen("trapezoid.in","r",stdin);
// freopen("trapezoid.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
top.push_back({a[i],i});
top.push_back({b[i],i});
bot.push_back({c[i],i});
bot.push_back({d[i],i});
}
sort(top.begin(),top.end());
sort(bot.begin(),bot.end());
BIT t(bot.size()+7);
for(pair<int,int>p:top){
int x=p.fi;
int i=p.se;
if(x==a[i]){
int x=id(c[i],bot)-1;
pair<int,int>tmp=t.get(x);
ans[i]={tmp.fi+1,tmp.se};
}
else if(x==b[i]){
int x=id(d[i],bot);
t.up(x,ans[i]);
}
}
pair<int,int>res={0,0};
for(int i=1;i<=n;i++){
res=cmax(res,ans[i]);
}
cout<<res.fi<<" "<<res.se;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |