제출 #1007639

#제출 시각아이디문제언어결과실행 시간메모리
1007639doducanh사다리꼴 (balkan11_trapezoid)C++17
45 / 100
1099 ms8472 KiB
#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=1e9+7; void 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; } } 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 { private: int n; vector<pair<int,int>>t; public: BIT(){} BIT(int n):n(n),t(n+7,make_pair(0,1)){} void up(int x,pair<int,int> val){ for(;x<=n;x+=(x&(-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)))cmax(res,t[x]); return res; } }; vector<int>a,b,c,d; int n; pair<int,int>ans[maxn]; main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; a.resize(n+1);b.resize(n+1); c.resize(n+1);d.resize(n+1); vector<pair<int,int>>top; vector<pair<int,int>>bot; 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(begin(top),end(top)); sort(begin(bot),end(bot)); bot.erase(unique(begin(bot),end(bot)),end(bot)); BIT t(bot.size()+7); for(auto[x,i]:top){ if(x==a[i]){ pair<int,int>tmp=t.get(id(c[i],bot)-1); ans[i]={tmp.fi+1,tmp.se}; } else if(x==b[i]){ t.up(id(d[i],bot),ans[i]); } } pair<int,int>res={0,0}; for(int i=1;i<=n;i++){ cmax(res,ans[i]); } cout<<res.fi<<" "<<res.se; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...