# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
309499 | caoash | 사다리꼴 (balkan11_trapezoid) | C++14 | 376 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
const int MX = 100005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;
namespace output {
void pr(int x) {
cout << x;
}
void pr(long x) {
cout << x;
}
void pr(ll x) {
cout << x;
}
void pr(unsigned x) {
cout << x;
}
void pr(unsigned long x) {
cout << x;
}
void pr(unsigned long long x) {
cout << x;
}
void pr(float x) {
cout << x;
}
void pr(double x) {
cout << x;
}
void pr(long double x) {
cout << x;
}
void pr(char x) {
cout << x;
}
void pr(const char * x) {
cout << x;
}
void pr(const string & x) {
cout << x;
}
void pr(bool x) {
pr(x ? "true" : "false");
}
template < class T1, class T2 > void pr(const pair < T1, T2 > & x);
template < class T > void pr(const T & x);
template < class T, class...Ts > void pr(const T & t,
const Ts & ...ts) {
pr(t);
pr(ts...);
}
template < class T1, class T2 > void pr(const pair < T1, T2 > & x) {
pr("{", x.f, ", ", x.s, "}");
}
template < class T > void pr(const T & x) {
pr("{"); // const iterator needed for vector<bool>
bool fst = 1;
for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0;
pr("}");
}
void ps() {
pr("\n");
} // print w/ spaces
template < class T, class...Ts > void ps(const T & t,
const Ts & ...ts) {
pr(t);
if (sizeof...(ts)) pr(" ");
ps(ts...);
}
void pc() {
cout << "]" << endl;
} // debug w/ commas
template < class T, class...Ts > void pc(const T & t,
const Ts & ...ts) {
pr(t);
if (sizeof...(ts)) pr(", ");
pc(ts...);
}
#define dbg(x...) pr("[", #x, "] = ["), pc(x);
}
#ifdef LOCAL
using namespace output;
#endif
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash{
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
map<int, int> cx, cy;
map<pi, pi> st;
map<pi, int> dp;
template<int SZ> struct Seg {
int tree[4*SZ];
int merge(int a, int b){
return max(a, b);
}
void update(int v, int l, int r, int i, int x) {
if (i > r || i < l) {
return;
} else if (l == r) {
tree[v] = x;
return;
} else {
int m = (l + r) / 2;
update(2 * v + 1, l, m, i, x);
update(2 * v + 2, m + 1, r, i, x);
tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
}
}
int query(int v, int l, int r, int ql, int qr) {
if (l > qr || r < ql) {
return 0;
} else if (l >= ql && r <= qr) {
return tree[v];
} else {
int m = (l + r) / 2;
int a = query(2 * v + 1, l, m, ql, qr);
int b = query(2 * v + 2, m + 1, r, ql, qr);
return merge(a, b);
}
}
};
Seg<MX> orz;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<pair<pi, pi>> vals(n);
vi xs, ys;
for (int i = 0; i < n; i++) {
cin >> vals[i].f.f >> vals[i].f.s;
cin >> vals[i].s.f >> vals[i].s.s;
xs.pb(vals[i].f.f), ys.pb(vals[i].s.f);
xs.pb(vals[i].f.s), ys.pb(vals[i].s.s);
}
sort(all(xs));
sort(all(ys));
int pt = 0;
for (auto v : xs) cx[v] = pt++;
pt = 0;
for (auto v : ys) cy[v] = pt++;
vector<pair<pi, int>> evts;
for (auto v : vals) {
pi lf = mp(cx[v.f.f], cy[v.s.f]);
pi sf = mp(cx[v.f.s], cy[v.s.s]);
// dbg(v, lf, sf);
st[sf] = lf;
evts.pb(mp(lf, 0));
evts.pb(mp(sf, 1));
}
sort(all(evts));
for (auto curr : evts) {
if (curr.s) {
dp[curr.f] = dp[st[curr.f]];
orz.update(0, 0, sz(cy), curr.f.s, dp[curr.f]);
} else {
dp[curr.f] = orz.query(0, 0, sz(cy), 0, curr.f.s) + 1;
}
// dbg(curr.f, curr.s, st[curr.f], dp[curr.f]);
}
int ans = orz.query(0, 0, sz(cy), 0, sz(cy));
cout << ans << " " << 1 << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |