# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
684854 | thiago_bastos | 사다리꼴 (balkan11_trapezoid) | C++17 | 229 ms | 25764 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;
const int MOD = 30013;
ii op(ii a, ii b) {
if(a.fi != b.fi) return max(a, b);
a.sc += b.sc;
if(a.sc >= MOD) a.sc -= MOD;
return a;
}
struct BIT2D {
vector<vector<int>> Y;
vector<int> X;
vector<vector<ii>> bit;
BIT2D() {}
BIT2D(vector<ii> p) {
for(auto [i, j] : p) X.pb(i);
sort(all(X));
X.resize(unique(all(X)) - X.begin());
Y.resize(X.size() + 1);
sort(all(p), [](auto a, auto b) {return a.sc < b.sc;});
for(auto [i, j] : p) {
for(int k = findPos(X, i); k < (int)Y.size(); k += k & -k)
if(Y[k].empty() || Y[k].back() != j) Y[k].pb(j);
}
bit.resize(Y.size());
for(int i = 0; i < (int)Y.size(); ++i) bit[i].assign(Y[i].size() + 1, ii(0, 0));
}
int findPos(vector<int>& coords, int v) {
return upper_bound(all(coords), v) - coords.begin();
}
void upd(int i, int j, ii v) {
for(int x = findPos(X, i); x < (int)bit.size(); x += x & -x)
for(int y = findPos(Y[x], j); y < (int)bit[x].size(); y += y & -y)
bit[x][y] = op(bit[x][y], v);
}
ii query(int i, int j) {
ii ans = {0, 1};
for(int x = findPos(X, i); x > 0; x -= x & -x)
for(int y = findPos(Y[x], j); y > 0; y -= y & -y)
ans = op(ans, bit[x][y]);
return ans;
}
};
void solve() {
int n;
cin >> n;
vector<tuple<int, int, int, int>> t(n);
vector<ii> query;
for(auto& [a, b, c, d] : t) {
cin >> a >> b >> c >> d;
query.pb({b, d});
}
sort(all(t), [](auto p, auto q) {
return min(get<0>(p), get<1>(p)) < min(get<0>(q), get<1>(q));
});
BIT2D bit(query);
ii ans {};
for(auto [a, b, c, d] : t) {
auto [dp, cnt] = bit.query(a - 1, c - 1);
++dp;
bit.upd(b, d, {dp, cnt});
ans = op(ans, {dp, cnt});
}
cout << ans.fi << ' ' << ans.sc << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |