# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1017476 | dosts | 사다리꼴 (balkan11_trapezoid) | C++17 | 140 ms | 39104 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int N = 1e6+1,inf = 2e9,B = 23,MOD = 30013,LIM = 1e9;
struct TRAP {
int a,b,c,d;
};
vi v;
int idx(int x){
return upper_bound(all(v),x)-v.begin();
}
struct MFT {
int n;
vi bit;
MFT(int nn) {
n = nn;
bit.assign(n+1,0);
}
void put(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = max(bit[i],v);
}
int get(int p) {
int ans = 0;
for (int i=p;i>0;i-=i&-i) ans = max(ans,bit[i]);
return ans;
}
};
int add(int x,int y) {
return ((x+y) >= MOD ? x+y-MOD : x+y);
}
struct SFT {
int n;
vi bit;
SFT(int nn) {
n = nn;
bit.assign(n+1,0);
}
void put(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = add(bit[i],v);
}
void set(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i] = v;
}
int get(int p) {
int ans = 0;
for (int i=p;i>0;i-=i&-i) ans = add(ans,bit[i]);
return ans;
}
};
void solve() {
int n;
cin >> n;
vector<TRAP> trap(n+1);
for (int i=1;i<=n;i++) cin >> trap[i].a >> trap[i].b >> trap[i].c >> trap[i].d;
for (int i=1;i<=n;i++) {
v.push_back(trap[i].a);
v.push_back(trap[i].b);
v.push_back(trap[i].c);
v.push_back(trap[i].d);
}
sort(v.begin(),v.end());
v.erase(unique(all(v)),v.end());
for (int i=1;i<=n;i++) {
trap[i].a = idx(trap[i].a);
trap[i].b = idx(trap[i].b);
trap[i].c = idx(trap[i].c);
trap[i].d = idx(trap[i].d);
}
int sz = v.size();
MFT mft(sz);
vi dp(n+1,0);
vi in[sz+1],out[sz+1];
for (int i=1;i<=n;i++) in[trap[i].a].push_back(i);
for (int i=1;i<=n;i++) out[trap[i].b].push_back(i);
for (int i=1;i<=sz;i++) {
for (auto it : in[i]) dp[it] = mft.get(trap[it].c)+1;
for (auto it : out[i]) mft.put(trap[it].d,dp[it]);
}
int mx = *max_element(dp.begin()+1,dp.end());
vi x[n+1];
for (int i=1;i<=n;i++) x[dp[i]].push_back(i);
vi ways(n+1,0);
for (auto it : x[1]) ways[it] = add(ways[it],1);
SFT sft(sz);
for (int i=2;i<=n;i++) {
vector<pii> vv;
for (auto it : x[i-1]) vv.push_back({trap[it].b,it});
for (auto it : x[i]) vv.push_back({trap[it].a,it});
sort(vv.begin(),vv.end());
for (auto it : vv) {
if (dp[it.ss] == i) ways[it.ss] = add(ways[it.ss],sft.get(trap[it.ss].c));
else sft.put(trap[it.ss].d,ways[it.ss]);
}
for (auto it : vv) sft.set(trap[it.ss].d,0);
}
int ans = 0;
for (int i=1;i<=n;i++) if (dp[i] == mx) ans = add(ans,ways[i]);
cout << mx sp ans << '\n';
//SERIFEFEDARTAR ORZ
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
/* #else
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout); */
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |