oj.uz

Submission #1058569

# Submission time Handle Problem Language Result Execution time Memory
1058569 2024-08-14T11:05:40 Z pubin06 trapezoid (balkan11_trapezoid) C++14
43 / 100
 84 ms 12760 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MAXn = 100005, MOD = 2023;
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;
}

Compilation message

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
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Partially correct 1 ms 6492 KB Partially correct
3 Partially correct 1 ms 6492 KB Partially correct
4 Partially correct 1 ms 6492 KB Partially correct
5 Partially correct 2 ms 6716 KB Partially correct
6 Partially correct 2 ms 6748 KB Partially correct
7 Partially correct 3 ms 6764 KB Partially correct
8 Partially correct 4 ms 6968 KB Partially correct
9 Partially correct 8 ms 7320 KB Partially correct
10 Partially correct 15 ms 7920 KB Partially correct
11 Partially correct 22 ms 8292 KB Partially correct
12 Partially correct 41 ms 9844 KB Partially correct
13 Partially correct 50 ms 10200 KB Partially correct
14 Partially correct 57 ms 10996 KB Partially correct
15 Partially correct 64 ms 11736 KB Partially correct
16 Partially correct 72 ms 11788 KB Partially correct
17 Partially correct 74 ms 11728 KB Partially correct
18 Partially correct 67 ms 12048 KB Partially correct
19 Partially correct 75 ms 12756 KB Partially correct
20 Partially correct 84 ms 12760 KB Partially correct