oj.uz

Submission #981119

# Submission time Handle Problem Language Result Execution time Memory
981119 2024-05-12T20:41:08 Z shadow_sami Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 846 ms 52940 KB 
#include<bits/stdc++.h>
#include "jumps.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
 
// ==========================(debug)============================================================================================== //
 
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
 
// void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
 
// ==========================(debug)============================================================================================== //
 
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 2e5+5;
const ll mod = 1e9+7;
 
bool f = false;
ll a[mx];
stack<ll> sck;
ll lefte[mx],righte[mx];
ll low[mx][20];
ll high[mx][20];
ll to[mx][20];
ll id[mx];
 
// void deb(){
// 	priority_queue<pi,vector<pi>,greater<pi>> k2 = pq;
// 	while(k2.size()){
// 		cout<<k2.top().ff<<" "<<k2.top().ss<<nli;
// 		k2.pop();
// 	}
// 	return ;
// }
 
void emptify(){
	while(sck.size())
		sck.pop();
	return;
}
 
void init(ll aa,vi v){
	n = aa;
	fip(0,n){
		a[i] = v[i],lefte[i] = righte[i] = -1;;
		id[a[i]] = i;
	}
	emptify();
	fip(0,n){
		while(sck.size() && a[i] > a[sck.top()])
			sck.pop();
		if(sck.size())
			lefte[i] = sck.top();
		else
			lefte[i] = i;
		sck.push(i);
	}
	emptify();
	fin(n-1,0){
		while(sck.size() && a[i] > a[sck.top()])
			sck.pop();
		if(sck.size())
			righte[i] = sck.top();
		else
			righte[i] = i;
		sck.push(i);
	}
	fip(0,n){
		to[i][0] = lefte[i];
		if(a[lefte[i]] > a[righte[i]]){
			high[i][0] = lefte[i];
			low[i][0] = righte[i];
		}else{
			high[i][0] = righte[i];
			low[i][0] = lefte[i];
		}
	}		
	fjp(1,20){
		fip(0,n){			
			to[i][j] = to[to[i][j-1]][j-1];			
			high[i][j] = high[high[i][j-1]][j-1];			
			low[i][j] = low[low[i][j-1]][j-1];
		}
	}
	return;
}
 
// ll calc(ll sr,ll de,ll na){
// 	if(sr==de)
// 		return na;
// 	fin(19,0){
// 		if(a[high[sr][i]] < a[de]){
// 			sr = high[sr][i];
// 			na |= (1<<i);
// 		}
// 	}
// 	if(a[high[sr][0]]==a[de])
// 		return na + 1;
// 	if(a[low[sr][0]]==a[de])
// 		return na + 1;
// 	fin(19,0){
// 		if(a[low[sr][i]] < a[de]){
// 			sr = low[sr][i];
// 			na |= (1<<i);
// 		}
// 	}
// 	if(a[low[sr][0]]==a[de])
// 		return na + 1;
// 	return -1;
// }

ll get(ll aa,ll b,ll x){
	if(a[b] > x)
		return -1;
	fjn(19,0)
		if(to[b][j]>=aa && a[to[b][j]]<x){			
			b = to[b][j];
		}
	return b;
}
 
ll minimum_jumps(ll b,ll c,ll d,ll e){
	ll nas = 0;
	tp = get(d,e,1e9);
	tp2 = get(b,c,a[tp]);	
	if(tp2==-1)
		return -1;
	if(tp2==tp-1)
		return 1;	
	tptp = get(c+1,d-1,1e9);	

	if(a[tptp]>a[tp])
		return -1;
	if(a[tptp]<a[tp2])
		return 1;
	fin(19,0){
		if(a[high[tp2][i]] <= a[tptp]){
			tp2 = high[tp2][i];
			nas |= (1<<i);
		}
	}
	if(a[tp2]==a[tptp])
		return nas+1;
	if(a[high[tp2][0]]<a[tp])
		return nas+2;
	fin(19,0){
		if(a[low[tp2][i]] <= a[tptp]){
			tp2 = low[tp2][i];
			nas |= (1<<i);
		}
	}
	return nas+1;
}
 
// int main(){
//     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen("input1.txt", "r", stdin);
//         freopen("output1.txt", "w", stdout);
//         freopen("error1.txt", "w", stderr);
//     #endif // ONLINE_JUDGE
 
//         ll aa;
//         cin>>aa;
//         vi bb(aa);
//         ll q;
//         cin>>q;
//         fip(0,aa)
//         	cin>>bb[i];
//         init(aa,bb);
        
//         while(q--){
//         	ll b,c,d,e;
//         	cin>>b>>c>>d>>e;
//         	cout<<minimum_jumps(b,c,d,e)<<nli;
//         }
        
//     cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
//     return 0;
// }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8544 KB Output is correct
3 Correct 138 ms 48176 KB Output is correct
4 Correct 812 ms 52696 KB Output is correct
5 Correct 661 ms 34896 KB Output is correct
6 Correct 806 ms 52916 KB Output is correct
7 Correct 624 ms 43672 KB Output is correct
8 Correct 846 ms 52940 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Incorrect 2 ms 8536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Incorrect 2 ms 8536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 64 ms 49444 KB Output is correct
6 Correct 72 ms 51928 KB Output is correct
7 Correct 37 ms 34384 KB Output is correct
8 Correct 71 ms 51908 KB Output is correct
9 Correct 8 ms 17456 KB Output is correct
10 Correct 75 ms 51908 KB Output is correct
11 Correct 69 ms 52876 KB Output is correct
12 Correct 66 ms 52536 KB Output is correct
13 Correct 66 ms 52856 KB Output is correct
14 Correct 70 ms 51996 KB Output is correct
15 Correct 83 ms 52392 KB Output is correct
16 Correct 69 ms 52720 KB Output is correct
17 Correct 75 ms 52592 KB Output is correct
18 Correct 1 ms 8536 KB Output is correct
19 Correct 1 ms 8536 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8536 KB Output is correct
22 Correct 2 ms 8536 KB Output is correct
23 Correct 1 ms 8536 KB Output is correct
24 Correct 1 ms 8536 KB Output is correct
25 Correct 1 ms 8536 KB Output is correct
26 Correct 1 ms 8536 KB Output is correct
27 Correct 2 ms 10584 KB Output is correct
28 Correct 2 ms 10584 KB Output is correct
29 Correct 2 ms 10584 KB Output is correct
30 Correct 2 ms 10584 KB Output is correct
31 Correct 2 ms 10584 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct
33 Correct 77 ms 51916 KB Output is correct
34 Correct 76 ms 52092 KB Output is correct
35 Correct 67 ms 52672 KB Output is correct
36 Correct 77 ms 52088 KB Output is correct
37 Incorrect 80 ms 52504 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 159 ms 32352 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 159 ms 32352 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8544 KB Output is correct
3 Correct 138 ms 48176 KB Output is correct
4 Correct 812 ms 52696 KB Output is correct
5 Correct 661 ms 34896 KB Output is correct
6 Correct 806 ms 52916 KB Output is correct
7 Correct 624 ms 43672 KB Output is correct
8 Correct 846 ms 52940 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Correct 2 ms 8536 KB Output is correct
14 Incorrect 2 ms 8536 KB Output isn't correct
15 Halted 0 ms 0 KB -