oj.uz

답안 #217836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217836 2020-03-31T02:03:26 Z MohamedAhmed04 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 255 ms 18856 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][1] , 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(v[p.second][3] , 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][1] , i}) ;
	}
	return cout<<ans<<" "<<cnt<<"\n" , 0 ;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2944 KB Output is correct
5 Correct 9 ms 3072 KB Output is correct
6 Correct 12 ms 3200 KB Output is correct
7 Correct 12 ms 3328 KB Output is correct
8 Correct 15 ms 3584 KB Output is correct
9 Correct 25 ms 4416 KB Output is correct
10 Correct 42 ms 6068 KB Output is correct
11 Correct 56 ms 6708 KB Output is correct
12 Correct 114 ms 10800 KB Output is correct
13 Correct 140 ms 12476 KB Output is correct
14 Correct 163 ms 13992 KB Output is correct
15 Correct 193 ms 14888 KB Output is correct
16 Correct 210 ms 15928 KB Output is correct
17 Correct 206 ms 16552 KB Output is correct
18 Correct 183 ms 17200 KB Output is correct
19 Correct 213 ms 17968 KB Output is correct
20 Correct 255 ms 18856 KB Output is correct