oj.uz

답안 #217831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217831 2020-03-31T00:48:04 Z MohamedAhmed04 사다리꼴 (balkan11_trapezoid) C++14
30 / 100
 188 ms 21224 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] ;

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) ;
	int ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		LIS[i] = tree.query(v[i][2]-1) + 1 ;
		ans = max(ans , LIS[i]) ;
		tree.update(v[i][3] , LIS[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 ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x = treecnt[LIS[i]-1].query(v[i][2]-1) ;
		if(LIS[i] == ans)
			cnt = (cnt + x) % mod ;
		treecnt[LIS[i]].update(v[i][3] , x) ;
	}
	return cout<<ans<<" "<<cnt<<"\n" , 0 ;
}

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Incorrect 8 ms 2816 KB Output isn't correct
4 Correct 7 ms 2816 KB Output is correct
5 Incorrect 8 ms 3072 KB Output isn't correct
6 Incorrect 11 ms 3200 KB Output isn't correct
7 Correct 11 ms 3456 KB Output is correct
8 Incorrect 13 ms 3584 KB Output isn't correct
9 Incorrect 21 ms 4544 KB Output isn't correct
10 Correct 34 ms 6332 KB Output is correct
11 Incorrect 43 ms 7220 KB Output isn't correct
12 Incorrect 87 ms 11820 KB Output isn't correct
13 Incorrect 109 ms 13612 KB Output isn't correct
14 Incorrect 131 ms 15528 KB Output isn't correct
15 Incorrect 137 ms 16300 KB Output isn't correct
16 Incorrect 150 ms 17372 KB Output isn't correct
17 Incorrect 156 ms 18236 KB Output isn't correct
18 Correct 148 ms 19112 KB Output is correct
19 Incorrect 159 ms 19920 KB Output isn't correct
20 Incorrect 188 ms 21224 KB Output isn't correct