oj.uz

Submission #217833

# Submission time Handle Problem Language Result Execution time Memory
217833 2020-03-31T01:59:09 Z MohamedAhmed04 trapezoid (balkan11_trapezoid) C++14
30 / 100
 208 ms 19224 KB 
#include <bits/stdc++.h>

using namespace std ;

const int mod = 30013 ;
const int MAX = 1e5 + 10 ;

struct segment_tree
{
	vector<int>v ;
	vector<long long> tree ;
	int sz ;
	bool flag ;
	void init(vector<int>v2 , bool t)
	{
		if(t == 0)
			flag = 0 ;
		else
			flag = 1 ;
		sz = (int)v2.size() ;
		v = v2 ;
		sort(v.begin() , v.end()) ;
		tree.resize(sz*4+10) ;
		for(int i = 0 ; i <= sz*4 ; ++i)
			tree[i] = 0 ;
	}
	int getidx1(long long idx)
	{
		int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
		return idx2 ;
	}
	int getidx2(long long idx)
	{
		int idx2 = upper_bound(v.begin() , v.end() , idx) - v.begin() ;
		idx2-- ;
		return idx2 ;
	}
	void update(int node , int l , int r , int idx , long long v)
	{
		if(idx > r || idx < l || idx < 0)
			return ;
		if(l == r)
		{
			if(flag == 0)
				tree[node] = max(tree[node] , v) ;
			else
				tree[node] = (tree[node] + v) % mod ;
			return ;
		}
		int mid = (l + r) >> 1 ;
		update(node << 1 , l , mid , idx , v) ;
		update(node << 1 | 1 , mid+1 , r , idx , v) ;
		if(flag == 0)
			tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
		else
			tree[node] = (tree[node << 1] + tree[node << 1 | 1]) % mod ;
	}
 
	long long query(int node , int l , int r , int from , int to)
	{
		if(from > r || to < l || from > to)
			return 0 ;
		if(l >= from && r <= to)
			return tree[node] ;
		int mid = (l + r) >> 1 ;
		long long a = query(node << 1 , l , mid , from , to) ;
		long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
		if(flag == 0)
			return max(a , b) ;
		else
			return (a + b) % mod ;
	}
 
	void update(long long idx , long long val)
	{
		idx = getidx1(idx) ;
		update(1 , 0 , sz , idx , val) ;
	}
 
	long long query(long long idx)
	{
		idx = getidx2(idx) ;
		return query(1 , 0 , sz , 0 , idx) ;
	}
};


int arr[MAX] ;
int n ;

vector< array<int , 4> >v ;
vector<int>v2 ;
vector<int>lis[MAX] ;
int LIS[MAX] , ways[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
	{
		int l1 , r1 , l2 , r2 ;
		cin>>l1>>r1>>l2>>r2 ;
		v.push_back({l1 , r1 , l2 , r2}) ;
		v2.push_back(r2) ;
	}
	sort(v.begin() , v.end()) ;
	segment_tree tree ;
	tree.init(v2 , 0) ;
	set< pair<int , int> >s ;
	int ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		while(s.size() > 0)
		{
			pair<int , int>p = *s.begin() ;
			if(p.first >= v[i][0])
				break ;
			tree.update(v[p.second][3] , LIS[p.second]) ;
			s.erase(p) ;
		}
		LIS[i] = tree.query(v[i][2]-1) + 1 ;
		ans = max(ans , LIS[i]) ;
		s.insert({v[i][3] , i}) ;
		lis[LIS[i]].push_back(v[i][3]) ;
	}
	vector<segment_tree>treecnt(n+1) ;
	treecnt[0].init({-1} , 1) ;
	treecnt[0].update(-1 , 1) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(lis[i].size())
			treecnt[i].init(lis[i] , 1) ;
	}
	int cnt = 0 ;
	s.clear() ;
	for(int i = 0 ; i < n ; ++i)
	{
		while(s.size() > 0)
		{
			pair<int , int>p = *s.begin() ;
			if(p.first >= v[i][0])
				break ;
			treecnt[LIS[p.second]].update(p.first , ways[p.second]) ;
			s.erase(p) ;
		}
		ways[i] = treecnt[LIS[i]-1].query(v[i][2]-1) ;
		if(LIS[i] == ans)
			cnt = (cnt + ways[i]) % mod ;
		s.insert({v[i][3] , i}) ;
	}
	return cout<<ans<<" "<<cnt<<"\n" , 0 ;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Incorrect 6 ms 2816 KB Output isn't correct
4 Correct 8 ms 2816 KB Output is correct
5 Incorrect 8 ms 3072 KB Output isn't correct
6 Incorrect 10 ms 3328 KB Output isn't correct
7 Correct 13 ms 3328 KB Output is correct
8 Incorrect 14 ms 3712 KB Output isn't correct
9 Incorrect 21 ms 4416 KB Output isn't correct
10 Correct 42 ms 6064 KB Output is correct
11 Incorrect 49 ms 7092 KB Output isn't correct
12 Incorrect 90 ms 10796 KB Output isn't correct
13 Incorrect 122 ms 13744 KB Output isn't correct
14 Incorrect 144 ms 15380 KB Output isn't correct
15 Incorrect 166 ms 14888 KB Output isn't correct
16 Incorrect 181 ms 16300 KB Output isn't correct
17 Incorrect 192 ms 16940 KB Output isn't correct
18 Correct 187 ms 17192 KB Output is correct
19 Incorrect 179 ms 19112 KB Output isn't correct
20 Incorrect 208 ms 19224 KB Output isn't correct