oj.uz

Submission #573000

# Submission time Handle Problem Language Result Execution time Memory
573000 2022-06-05T15:38:22 Z StrawHatWess Event Hopping (BOI22_events) C++17
0 / 100
 341 ms 7824 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int>vi; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF=2e9;
const int MX=1e5+10; 



void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////


int N,Q; 
vi L(MX), R(MX);  

bool cmp(int i, int j){
	if(R[i]!=R[j]) return R[i] < R[j];
	return L[i] > L[j];  
}

int main(){
	IO(); 

	cin>>N>>Q; 

	FOR(i,0,N) cin>>L[i]>>R[i]; 

	vi vec(N); iota(all(vec),0); 
	sort(all(vec),cmp); 

	//for(int x: vec) cout << x << " "; cout << endl;

	unordered_map<int,int>mp; 
	FOR(i,0,N) mp[vec[i]]=i; 

	vi jump(N), jump_val(N); 
	int mnl=INF, mnl_idx; 
	ROF(j,0,N){
		int i=vec[j]; 
		if(mnl<=R[i]){
			jump[i]=jump[mnl_idx]; 
			jump_val[i]=jump_val[mnl_idx]+1; 
		}
		else{
			jump[i]=i; 
			jump_val[i]=0; 
		}

		if(ckmin(mnl,L[i])) mnl_idx=i; 
	}

	//for(int x: jump_val) cout << x << " "; cout << endl;

	while(Q--){
		int s,e; cin>>s>>e; s--; e--; 
		//s=mp[s], e=mp[e]; 

		//cout << s << " " << e << endl;

		if(jump[s]==jump[e] && jump_val[s]>=jump_val[e]) cout << jump_val[s] - jump_val[e] << endl;
		else cout << "impossible" << endl;
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:57:24: warning: 'mnl_idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |    jump[i]=jump[mnl_idx];
      |                        ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 7328 KB Output is correct
2 Correct 341 ms 7276 KB Output is correct
3 Correct 262 ms 7328 KB Output is correct
4 Correct 270 ms 7824 KB Output is correct
5 Correct 272 ms 7672 KB Output is correct
6 Incorrect 266 ms 7464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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