Submission #549280

#	Time	Username	Problem	Language	Result	Execution time	Memory
549280		Bungmint	trapezoid (balkan11_trapezoid)	C++17	30 / 100	155 ms	21464 KiB

trapezoid

//Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}

template<typename T, typename Merge = plus<T>>
struct SegTree{
	int sz;
	const Merge merge;
	vector<T> t;
	SegTree(int n) : merge(Merge()) {
		sz = 1;
		while (sz<n) sz*=2;
		t.resize(sz*2);
	}
	void build(vector<T> &vec, int x, int l, int r)
	{
	    if (r - l == 1)
	    {
	        if (l < (int)vec.size())
	            t[x] = vec[l];
	        return;
	    }
	    int mid = (l + r) / 2;
	    build(vec, 2 * x + 1, l, mid);
	    build(vec, 2 * x + 2, mid, r);
	    t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
	void build(vector<T> &vec)
	{
	    build(vec, 0, 0, sz);
	}
	void upd(int i, const T& v, int x, int l, int r)
	{
	    if (r - l == 1)
	    {
	        t[x] = v;
	        return;
	    }
	    int mid = (l + r) / 2;
	    if (i < mid)
	        upd(i, v, 2 * x + 1, l, mid);
	    else
	        upd(i, v, 2 * x + 2, mid, r);
	    t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
	void upd(int i, const T& v)
	{
	    upd(i, v, 0, 0, sz);
	}
	T query(int l, int r, int x, int lx, int rx)
	{
	    if (lx >= r || rx <= l)
	        return T();
	    if (lx >= l && rx <= r)
	        return t[x];
	    int mid = (lx + rx) / 2;
	    T a = query(l, r, 2 * x + 1, lx, mid);
	    T b = query(l, r, 2 * x + 2, mid, rx);
	    return merge(a, b);
	}
	T query(int l, int r)
	{
	    return query(l, r, 0, 0, sz);
	}
};

#define int long long
const int mod = 30013;
struct Node {
	int mx, cnt;
	Node(int x = 0, int c = 0) : mx(x), cnt(c) {}
	Node operator+(const Node& other) const {
		Node res = {};
		if (mx == other.mx) res.mx = mx, res.cnt = (cnt + other.cnt) % mod;
		else{
			if (mx > other.mx) res = *this;
			else res = other;
		}
		return res;
	}
};


vi xs, ys;
void insert_x(int x) {
	xs.pb(x);
}
void insert_y(int x) {
	ys.pb(x);
}
int get_x(int x) {
	return lb(all(xs), x) - xs.begin();
}
int get_y(int y) {
	return lb(all(ys), y) - ys.begin();
}
pii conv(pii a) {
	return {get_x(a.fi), get_y(a.se)};
}

void solve()
{
	int n;
	cin >> n;
	vector<pair<pii, pii>> a(n);
	vector<ar<int, 4>> todo;
	vector<Node> b(n);
	SegTree<Node> seg(2 * n + 2);
	for (auto &[x, y] : a) {
		cin >> x.fi >> x.se >> y.fi >> y.se;
		insert_x(x.fi), insert_x(x.se);
		insert_y(y.fi), insert_y(y.se);
	}
	insert_x(0); insert_y(0);
	insert_x(INF + 1), insert_y(INF + 1);
	pii st = {0, 0}, en = {INF + 1, INF + 1};
	sort(all(xs)), xs.resize(unique(all(xs)) - xs.begin());
	sort(all(ys)), ys.resize(unique(all(ys)) - ys.begin());
	F0R(i, n) {
		auto &[x, y] = a[i];
		x = conv(x), y = conv(y);
		todo.pb({x.fi, y.fi, 1, i});
		todo.pb({x.se, y.se, -1, i});
	}
	st = conv(st), en = conv(en);
	seg.upd(st.se, Node(0, 1));
	sort(all(todo));
	for (auto &[x, y, t, id] : todo) {
		if (t == -1) {
			seg.upd(y, b[id]);
		}else{
			b[id] = seg.query(0, y);
			b[id].mx++;
		}
	}
	Node ans = seg.query(0, en.se);
	cout << ans.mx << ' ' << ans.cnt << '\n';
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase=1;
    // cin >> testcase;	
    while (testcase--)
    {
        solve();
    }
}

Compilation message (stderr)

trapezoid.cpp: In function 'void setIO(std::string)':
trapezoid.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen((s + ".out").c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100