Submission #307285

#	Time	Username	Problem	Language	Result	Execution time	Memory
307285		shivensinha4	trapezoid (balkan11_trapezoid)	C++17	100 / 100	363 ms	63600 KiB

trapezoid

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int mod = 30013;

class SegmentTree {
	private:
		vector<int> tree;  int n;
		int bound = 0;
		
		int merge(int a, int b) {
			return max(a, b);
		}
		
		void update(int i, int val, int l, int r, int p) {
			if (l > i or r < i) return;
			if (l == r) {
				tree[p] = val;
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		int mx(int i, int j, int l, int r, int p) {
			if (l > j or r < i) return bound;
			if (l >= i and r <= j) return tree[p];
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return merge(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
		}
	
	public: 
		SegmentTree(int N) {
			n = N;
			tree.resize(4*n);
		}
		
		int mx(int i, int j) {
			return mx(i, j, 0, n-1, 0);
		}
		
		void update(int i, int val) {
			update(i, val, 0, n-1, 0);
		}
};

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
	private: vector<ll> tree; int n;
	int LSOne(int x) {
		return x&(-x);
	}

	public:
		BIT(int x) {
			n = x;
			tree.resize(n+1);
		}
		ll sum(int a) {
			ll sum = 0;
			for (; a > 0; a -= LSOne(a)) {
				sum += tree[a];
				if (sum >= mod) sum -= mod;
				if (sum < 0) sum += mod;
			}
			return sum;
		}
		ll sum(int a, int b) {
			ll ans = sum(b) - (a == 1 ? 0 : sum(a-1));
			if (ans >= mod) ans -= mod;
			if (ans < 0) ans += mod;
			return ans;
		}
		void update(int p, ll v) {
			for (; p < n+1; p += LSOne(p)) {
				tree[p] += v;
				if (tree[p] >= mod) tree[p] -= mod;
				if (tree[p] < 0) tree[p] += mod;
			}
		}
};

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<vi> pts(4*n, vi(2)), lines(2*n);
	vi raw(4*n);
	
	int lpt = 0;
	for_(i, 0, n) {
		for_(j, 4*i, 4*i+4) {
			cin >> pts[j][0];
			pts[j][1] = j;
		}
	}
	
	sort(pts.begin(), pts.end());
	int last = 0;
	for_(i, 0, pts.size()) {
		if (i == 0 or pts[i-1][0] != pts[i][0]) {
			raw[pts[i][1]] = i;
			last = i;
		} else raw[pts[i][1]] = last;
	}
	
	for_(i, 0, n) {
		lines[lpt++] = {raw[4*i], raw[4*i+2], i}; lines[lpt++] = {raw[4*i+1], raw[4*i+3], i}; 
	}
	
	sort(lines.begin(), lines.end());
	SegmentTree tree(last+1);
	
	vi v(n, -1), ct(n+1, -1);
	ct[n] = 1;
	vector<vector<vi>> withLenIn(n+1), withLenOut(n+1);
	withLenOut[0].push_back({-1, 0, n});
	lpt = 0;
	for (auto i: lines) {
		if (v[i[2]] == -1) {
			v[i[2]] = tree.mx(0, i[1]) + 1;
			//cout << i[2]+1 << " " << i[1] << " -> " << v[i[2]] << endl;
			withLenIn[v[i[2]]].push_back({lpt++, i[1], i[2]});
		}
		else {
			tree.update(i[1], v[i[2]]);
			withLenOut[v[i[2]]].push_back({lpt++, i[1], i[2]});
		}
	}
	
	
	BIT fenwick(last+1);
	int l = 0, count = 0;
	for_(i, 1, n+1) {
		if (!withLenIn[i].size()) break;
		//if (i == 1) {
			//for (auto t: withLenIn[i]) ct[t[2]] = 1;
			//continue;
		//} 
		
		//cout << "on " << i << endl;
		l = i; count = 0;
		int pt = 0;
		for (auto t: withLenIn[i]) {
			while (pt < withLenOut[i-1].size() and withLenOut[i-1][pt][0] < t[0]) {
				fenwick.update(withLenOut[i-1][pt][1]+1, ct[withLenOut[i-1][pt][2]]);
				pt++;
			}
			
			ct[t[2]] = fenwick.sum(t[1]+1);
			//cout << t[2] << " gets " << ct[t[2]] << endl;
			count += ct[t[2]];
			if (count >= mod) count -= mod;
		}
		
		for (pt = min(pt, (int) withLenOut[i-1].size())-1; pt >= 0; pt--) fenwick.update(withLenOut[i-1][pt][1]+1, -ct[withLenOut[i-1][pt][2]]);
	}
	
	cout << l << " " << count << endl;

	return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |    while (pt < withLenOut[i-1].size() and withLenOut[i-1][pt][0] < t[0]) {
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100