Submission #1058570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058570		pubin06	trapezoid (balkan11_trapezoid)	C++14	100 / 100	85 ms	10188 KiB

trapezoid

#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MAXn = 100005, MOD = 30013;
void add(int &X, int Y) {
	if ((X += Y) >= MOD) X -= MOD;
}

struct sth {
	int a, b, c, d;
} h[MAXn];
int n, k;
int val[(1 << 19) + 5], cnt[(1 << 19) + 5];
void update(int i, int v, int c) {
	int id = 1, l = -1, r = 2 * n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (i <= mid) {
			r = mid;
			id <<= 1;
		} else {
			l = mid + 1;
			id = id << 1 | 1;
		}
	}
	if (val[id] < v) {
		val[id] = v;
		cnt[id] = c;
	} else if (val[id] == v) add(cnt[id], c);
	while (id > 1) {
		id >>= 1;
		int Lv = val[id << 1], Rv = val[id << 1 | 1];
		val[id] = max(Lv, Rv);
		if (Lv < Rv) cnt[id] = cnt[id << 1 | 1];
		else if (Lv > Rv) cnt[id] = cnt[id << 1];
		else {
			cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
			if (cnt[id] >= MOD) cnt[id] -= MOD;
		}
	}
}
pair<int, int> get(int Rt) {
	int v = -1, c = 0;
	int id = 1, l = -1, r = 2 * n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (Rt <= mid) {
			r = mid;
			id <<= 1;
		} else {
			if (v < val[id << 1]) c = cnt[id << 1];
			else if (v == val[id << 1]) add(c, cnt[id << 1]);
			v = max(v, val[id << 1]);
			l = mid + 1;
			id = id << 1 | 1;
		}
	}
	if (v < val[id]) c = cnt[id];
	else if (v == val[id]) add(c, cnt[id]);
	v = max(v, val[id]);
	return {v, c};
}
struct state {
	int t, x, id;
};
vector<state> vct;
int dp[MAXn], f[MAXn];

signed main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    #define TASK "TRAPEZ"
    if (ifstream(TASK".INP")) {
    	freopen(TASK".INP", "r", stdin);
    	freopen(TASK".OUT", "w", stdout);
    }
    
    cin >> n;
    vector<int> ne2;
    for (int i = 1, a, b, c, d; i <= n; i++) {
    	cin >> a >> b >> c >> d;
    	h[i] = {a, b, c, d};
    	ne2.emplace_back(c);
    	ne2.emplace_back(d);
    	vct.push_back({0, a, i});
    	vct.push_back({1, b, i});
    }
    sort(begin(ne2), end(ne2));
    ne2.resize(unique(begin(ne2), end(ne2)) - ne2.begin());
    for (int i = 1; i <= n; i++) {
    	h[i].c = lower_bound(begin(ne2), end(ne2), h[i].c) - ne2.begin();
    	h[i].d = lower_bound(begin(ne2), end(ne2), h[i].d) - ne2.begin();
    }
    sort(begin(vct), end(vct), [&] (const state &X, const state &Y) {
    	return X.x < Y.x;
    });
    memset(val, -1, sizeof val);
    for (int i = 0; i < sz(ne2); i++) update(i, -1, 0);
    update(-1, 0, 1);
    for (auto tt: vct) {
    	int id = tt.id;
    	if (!tt.t) {
    		pair<int, int> tmp = get(h[id].c - 1);
    		dp[id] = tmp.fi + 1;
    		f[id] = tmp.se;
    	} else {
    		update(h[id].d, dp[id], f[id]);
    	}
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) {
    	if (ans1 < dp[i]) {
    		ans1 = dp[i];
    		ans2 = f[i];
    	} else if (ans1 == dp[i]) add(ans2, f[i]);
    }
    cout << ans1 << ' ' << ans2;
    
    return 0;
}
// Revive! >:)

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:78:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |      freopen(TASK".INP", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:79:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |      freopen(TASK".OUT", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100