oj.uz

Submission #744623

# Submission time Handle Problem Language Result Execution time Memory
744623 2023-05-18T20:29:19 Z MohamedAhmed04 Osumnjičeni (COCI21_osumnjiceni) C++14
0 / 110
 115 ms 23736 KB 
#include <bits/stdc++.h>

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 2e5 + 10 ;

int L[MAX] , R[MAX] ;
int n , q ;

int val[MAX] ;

vector< pair<int , int> >queries[MAX] ;
int ans[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>L[i]>>R[i] ;
	cin>>q ;
	for(int i = 1 ; i <= q ; ++i)
	{
		int l , r ;
		cin>>l>>r ;
		queries[r].emplace_back(l , i) ;
	}
	set< array<int , 3> >s ;
	int last = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		auto it = s.lower_bound({L[i] , -1 , -1}) ;
		if(it != s.begin())
			--it ;
		while(s.size() && it != s.end())
		{
			array<int , 3>a = *it ;
			if(a[0] > R[i])
				break ;
			if(a[1] >= L[i])
				val[i] = max(val[i] , a[2]) ;
			++it ;
		}
		for(int j = last+1 ; j <= val[i] ; ++j)
			s.erase({L[j] , R[j] , j}) ;
		last = max(last , val[i]) ;
		s.insert({L[i] , R[i] , i}) ;
	}
	ordered_set< pair<int , int> >s2 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		s2.insert({val[i] , i}) ;
		for(auto &p : queries[i])
			ans[p.second] = 1 + s2.size() - s2.order_of_key({p.first , -1}) ;
	}
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 23008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 23736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 23008 KB Output isn't correct
2 Halted 0 ms 0 KB -