oj.uz

Submission #603160

# Submission time Handle Problem Language Result Execution time Memory
603160 2022-07-23T16:16:33 Z MohamedAhmed04 Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 12600 KB 
#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 2e5 + 10 ;

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

void compress()
{
	vector<int>v ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back(L[i]) , v.push_back(R[i]) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		L[i] = lower_bound(v.begin() , v.end() , L[i]) - v.begin() ;
		R[i] = lower_bound(v.begin() , v.end() , R[i]) - v.begin() ;
		L[i]++ , R[i]++ ;
	}
}

int dp[MAX] , ans[MAX] ;

vector< array<int , 3> >v ;

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

bool cmp(array<int , 3>&a , array<int , 3>&b)
{
	if(a[1] != b[1])
		return (a[1] < b[1]) ;
	else
		return (a[0] < b[0]) ;
}

void solve(int st)
{
	if(!queries[st].size())
		return ;
	for(int i = 1 ; i <= n ; ++i)
		dp[i] = inf ;
	dp[st] = 0 ;
	stack<int>s ;
	for(auto &a : v)
	{
		int l = a[0] , r = a[1] , idx = a[2] ;
		int last = -1 ;
		while(s.size() && R[s.top()] >= l)
		{
			last = s.top() ;
			s.pop() ;
		}
		if(last == -1 && idx != st)
			continue ;
		if(idx != st)
			s.push(last) , dp[idx] = dp[last] + 1 ;
		s.push(idx) ;
	}
	for(auto &p : queries[st])
		ans[p.second] = dp[p.first] ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>L[i]>>R[i] ;
	for(int i = 1 ; i <= q ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		queries[x].emplace_back(y , i) ;
	}
	compress() ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back({L[i] , R[i] , i}) ;
	sort(v.begin() , v.end() , cmp) ;
	for(int i = 1 ; i <= n ; ++i)
		solve(i) ;
	for(int i = 1 ; i <= q ; ++i)
	{
		if(ans[i] != inf)
			cout<<ans[i]<<"\n" ;
		else
			cout<<"impossible\n" ;
	}
	return 0 ;
}

Compilation message

events.cpp: In function 'void solve(int)':
events.cpp:50:18: warning: unused variable 'r' [-Wunused-variable]
   50 |   int l = a[0] , r = a[1] , idx = a[2] ;
      |                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 93 ms 12240 KB Output is correct
3 Correct 592 ms 12600 KB Output is correct
4 Execution timed out 1538 ms 12512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5052 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5056 KB Output is correct
8 Correct 4 ms 5052 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5052 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5056 KB Output is correct
8 Correct 4 ms 5052 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 4 ms 5076 KB Output is correct
13 Correct 5 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5056 KB Output is correct
16 Correct 4 ms 5016 KB Output is correct
17 Correct 4 ms 5096 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 51 ms 8180 KB Output is correct
20 Correct 48 ms 8204 KB Output is correct
21 Correct 188 ms 8724 KB Output is correct
22 Incorrect 223 ms 8848 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5052 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5056 KB Output is correct
8 Correct 4 ms 5052 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4972 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 4 ms 5048 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 84 ms 9644 KB Output is correct
20 Correct 151 ms 10012 KB Output is correct
21 Correct 173 ms 10588 KB Output is correct
22 Incorrect 128 ms 10656 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10908 KB Output is correct
2 Correct 570 ms 11220 KB Output is correct
3 Execution timed out 1532 ms 11208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 93 ms 12240 KB Output is correct
3 Correct 592 ms 12600 KB Output is correct
4 Execution timed out 1538 ms 12512 KB Time limit exceeded
5 Halted 0 ms 0 KB -