Submission #1288332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288332		shidou26	trapezoid (balkan11_trapezoid)	C++20	100 / 100	90 ms	9732 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 1e5 + 3;

int n;
array<int, 4> t[N];

void input() {
	cin >> n;

	for(int i = 1; i <= n; i++) {
		cin >> t[i][0] >> t[i][2] >> t[i][1] >> t[i][3];
	}
}

const int MOD = 30013;

namespace subtask_1 {
	bool approve() {
		return n <= 5000;
	}

	const int N = 5e3 + 3;

	pii dp[N];

	void execute() {
		sort(t + 1, t + 1 + n, [&](array<int, 4> u, array<int, 4> v) {
			return u[0] < v[0];
		});  

		for(int i = 1; i <= n; i++) {
			dp[i] = pii(1, 1);

			for(int j = 1; j < i; j++) {
				if(t[j][2] < t[i][0] && t[j][3] < t[i][1]) {
					if(dp[i].fi < dp[j].fi + 1) {
						dp[i].fi = dp[j].fi + 1;
						dp[i].se = dp[j].se;
					}else if(dp[i].fi == dp[j].fi + 1) {
						(dp[i].se += dp[j].se) %= MOD;
					}
				}
			}
		}

		// for(int i = 1; i <= n; i++) cout << dp[i] << endl;
			
		int answer = max_element(dp + 1, dp + 1 + n)->fi, way = 0;
		for(int i = 1; i <= n; i++) if(dp[i].fi == answer) (way += dp[i].se) %= MOD;
		cout << answer << " " << way << endl;
	}
}

namespace subtask_2 {
	bool approve() {
		return true;
	}

	vector<int> cps;
	priority_queue<pii, vector<pii>, greater<pii>> wait;
	pii dp[N];

	int compress(int v) {
		return lower_bound(all(cps), v) - cps.begin() + 1;
	}

	struct SegmentTree {
		vector<pii> tr;
		SegmentTree (int n) : tr(n << 2 | 3) {}

		pii pull(pii u, pii v) {
			if(u.fi == v.fi) 
				return pii(u.fi, (u.se + v.se) % MOD);
			return max(u, v);
		}

		void update(int id, int l, int r, int p, pii v) {
			if(l == r) {
				if(tr[id].fi < v.fi) tr[id] = v;
				else if(tr[id].fi == v.fi) tr[id] = {tr[id].fi, (tr[id].se + v.se) % MOD};
				return;
			}

			int mid = (l + r) >> 1;
			if(p <= mid) update(id << 1, l, mid, p, v);
			else update(id << 1 | 1, mid + 1, r, p, v);
			
			tr[id] = pull(tr[id << 1], tr[id << 1 | 1]);
		}

		pii get(int id, int l, int r, int u, int v) {
			if(u > v) return pii(0, 0);
			if(u <= l && r <= v) return tr[id];

			int mid = (l + r) >> 1;
			if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
			if(mid + 1 > v) return get(id << 1, l, mid, u, v);

			return pull(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
		}
	};

	void execute() {
		sort(t + 1, t + 1 + n, [&](array<int, 4> u, array<int, 4> v) {
			return u[0] < v[0];
		});  

		for(int i = 1; i <= n; i++) {
			cps.push_back(t[i][1]);
			cps.push_back(t[i][3]);
		}

		sort(all(cps)); filter(cps);		
		SegmentTree st(sz(cps));

		for(int i = 1; i <= n; i++) {
			dp[i] = pii(1, 1);
			// cout << dbg(t[i][0]) << dbg(t[i][1]) << dbg(t[i][2]) << dbg(t[i][3]) << endl;

			while(!wait.empty() && wait.top().fi < t[i][0]) {
				int j = wait.top().se;
				// cout << "Update " << dbg(t[j][3]) << dbg(compress(t[j][3])) << dbg(dp[j]) << endl;
				st.update(1, 1, sz(cps), compress(t[j][3]), dp[j]);
				wait.pop();
			}

			// cout << dbg(t[i][1]) << dbg(compress(t[i][1])) << endl;
			pii optimal = st.get(1, 1, sz(cps), 1, compress(t[i][1]));
			maximize(dp[i], pii(optimal.fi + 1, optimal.se));
			// cout << dbg(dp[i]) << endl;

			wait.emplace(t[i][2], i);
		}

		int answer = max_element(dp + 1, dp + 1 + n)->fi, way = 0;
		for(int i = 1; i <= n; i++) if(dp[i].fi == answer) (way += dp[i].se) %= MOD;
		cout << answer << " " << way << endl;
	}
}

void process() {
	// if(subtask_1::approve()) return subtask_1::execute();
	if(subtask_2::approve()) return subtask_2::execute();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int testcase = 1; // cin >> testcase;    
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100