oj.uz

Submission #307285

# Submission time Handle Problem Language Result Execution time Memory
307285 2020-09-27T14:34:55 Z shivensinha4 trapezoid (balkan11_trapezoid) C++17
100 / 100
 363 ms 63600 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 5 ms 1664 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 10 ms 2944 KB Output is correct
8 Correct 13 ms 3456 KB Output is correct
9 Correct 27 ms 6648 KB Output is correct
10 Correct 56 ms 13320 KB Output is correct
11 Correct 71 ms 16504 KB Output is correct
12 Correct 170 ms 32248 KB Output is correct
13 Correct 209 ms 38560 KB Output is correct
14 Correct 250 ms 45048 KB Output is correct
15 Correct 282 ms 47864 KB Output is correct
16 Correct 328 ms 50936 KB Output is correct
17 Correct 301 ms 54392 KB Output is correct
18 Correct 269 ms 57720 KB Output is correct
19 Correct 326 ms 60472 KB Output is correct
20 Correct 363 ms 63600 KB Output is correct