Submission #307160

#	Time	Username	Problem	Language	Result	Execution time	Memory
307160		shivensinha4	trapezoid (balkan11_trapezoid)	C++17	16 / 100	1098 ms	65540 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'

struct Node {
	ll mx, sum;
};

const ll mod = 30013;

class SegmentTree {
	private:
		vector<Node> tree;  int n;
		vi marked;
		Node bound = {0, 0};
		
		Node merge(Node a, Node b) {
			return (Node) {max(a.mx, b.mx), 0};
		}
		
		void push(int p) {
			if (!marked[p]) return;
			int c1 = 2*p+1, c2 = 2*p+2;
			marked[c1] = marked[c2] = true;
			if (tree[c1].mx == tree[p].mx) tree[c1].sum += tree[p].sum;
			else tree[c1].sum = tree[p].sum;
			
			if (tree[c2].mx == tree[p].mx) tree[c2].sum += tree[p].sum;
			else tree[c2].sum = tree[p].sum;
			
			tree[c1].mx = tree[c2].mx = tree[p].mx;
			tree[p].sum = 0;
			marked[p] = false;
		}
		
		void buildTree(int l, int r, int p) {
			if (l == r) {
				tree[p] = {0, 1};
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			buildTree(l, mid, c1); buildTree(mid+1, r, c2);
		}
		
		void update(int i, int j, ll val, ll ct, int l, int r, int p) {
			if (r < i or l > j) return;
			
			if (l >= i and r <= j and tree[p].mx <= val) {
				if (tree[p].mx < val) tree[p].sum = ct;
				else tree[p].sum += ct;
				
				tree[p].mx = val;
				marked[p] = true;
				return;
			} else if (l == r) return;
			
			push(p);
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, j, val, ct, l, mid, c1); update(i, j, val, ct, mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		ll getSum(int i, int l, int r, int p) {
			if (l > i or r < i) return 0;
			if (l == r) return tree[p].sum;
			
			push(p);
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return getSum(i, l, mid, c1) + getSum(i, mid+1, r, c2);
		}
		
		ll getVal(int i, int l, int r, int p) {
			if (l > i or r < i) return 0;
			if (marked[p] or l == r) {
				return tree[p].mx;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return max(getVal(i, l, mid, c1), getVal(i, mid+1, r, c2));
		}
	
	public: 
		SegmentTree(int N) {
			n = N;
			tree.resize(4*n);
			marked.resize(4*n);
			buildTree(0, n-1, 0);
		}
		
		ll getSum(int i) {
			return getSum(i, 0, n-1, 0);
		}
		
		ll getVal(int i) {
			return getVal(i, 0, n-1, 0);
		}
		
		void update(int i, int j, ll val, ll ct) {
			update(i, j, val, ct, 0, n-1, 0);
		}
};



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);
	for (auto i: lines) {
		if (v[i[2]] == -1) {
			v[i[2]] = tree.getVal(i[1]) + 1;
			ct[i[2]] = tree.getSum(i[1]);
			//cout << i[2]+1 << " " << i[1] << " -> " << v[i[2]] << " " << ct[i[2]] << endl;
		} else {
			tree.update(i[1], last, v[i[2]], ct[i[2]]);
			//cout << "setting " << i[2]+1 << " " << i[1] << " -> " << v[i[2]] << " " << ct[i[2]] << endl;
		}
	}
	
	cout << tree.getVal(last) << " " << tree.getSum(last) << endl;

	return 0;
}

• Subtask 1: 16 / 100