oj.uz

Submission #883715

# Submission time Handle Problem Language Result Execution time Memory
883715 2023-12-05T19:24:33 Z tsumondai trapezoid (balkan11_trapezoid) C++14
43 / 100
 97 ms 25012 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma comment(linker, "/stack:336777216")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define int long long

#define tl fi.fi
#define tr fi.se
#define dl se.fi
#define dr se.se
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5e5 + 5;

const int oo = 1e9, mod = 2023;

pair <ii, ii> a[N];

ii bit[N];
int n;
void update (int x, ii val) {
	for (; x <= 2 * n; x += x & -x)
		if (bit[x].fi < val.fi)
			bit[x] = val;
		else if (bit[x].fi == val.fi)
			bit[x].se = (bit[x].se + val.se) % mod;
}

ii get (int x) {
	ii ans = {0, 1};
	for (; x > 0; x -= x & -x)
		if (bit[x].fi > ans.fi)
			ans = bit[x];
		else if (bit[x].fi == ans.fi)
			ans.se = (ans.se + bit[x].se) % mod;
	return ans;
}

ii ret, res[N];
vector <int> t, d;
int g[N], u[N];

void process() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].tl >> a[i].tr >> a[i].dl >> a[i].dr;
		t.pb(a[i].tl);
		t.pb(a[i].tr);
		d.pb(a[i].dl);
		d.pb(a[i].dr);
	}
	sort(t.begin(), t.end());
	sort(d.begin(), d.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	d.erase(unique(d.begin(), d.end()), d.end());
	for (int i = 1; i <= n; ++i) {
		a[i].tl = lower_bound (t.begin(), t.end(), a[i].tl) - t.begin() + 1;
		a[i].tr = lower_bound (t.begin(), t.end(), a[i].tr) - t.begin() + 1;
		a[i].dl = lower_bound (d.begin(), d.end(), a[i].dl) - d.begin() + 1;
		a[i].dr = lower_bound (d.begin(), d.end(), a[i].dr) - d.begin() + 1;
		g[a[i].tl] = i;
		u[a[i].tr] = i;
	}
	for (int i = 1; i <= 2 * n; i++) {
		if (g[i]) {
			int v = g[i];
			ii f = get(a[v].dl);
			++f.fi;
			res[v] = f;
			if (f.fi > ret.fi)
				ret = f;
			else if (f.fi == ret.fi)
				ret.se = (ret.se + f.se) % mod;
		}
		else {
			int v = u[i];
			update(a[v].dr, res[v]);
		}
	}
	cout << ret.fi << " " << ret.se;
	return;
}


signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message

trapezoid.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:336777216")
      |

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Partially correct 1 ms 8540 KB Partially correct
3 Partially correct 2 ms 8540 KB Partially correct
4 Partially correct 2 ms 8540 KB Partially correct
5 Partially correct 3 ms 8796 KB Partially correct
6 Partially correct 4 ms 8796 KB Partially correct
7 Partially correct 5 ms 8824 KB Partially correct
8 Partially correct 5 ms 9052 KB Partially correct
9 Partially correct 10 ms 9432 KB Partially correct
10 Partially correct 18 ms 12108 KB Partially correct
11 Partially correct 24 ms 14516 KB Partially correct
12 Partially correct 59 ms 20764 KB Partially correct
13 Partially correct 67 ms 21436 KB Partially correct
14 Partially correct 69 ms 22444 KB Partially correct
15 Partially correct 75 ms 22960 KB Partially correct
16 Partially correct 82 ms 23404 KB Partially correct
17 Partially correct 89 ms 23732 KB Partially correct
18 Partially correct 82 ms 24112 KB Partially correct
19 Partially correct 87 ms 24316 KB Partially correct
20 Partially correct 97 ms 25012 KB Partially correct