oj.uz

Submission #981121

# Submission time Handle Problem Language Result Execution time Memory
981121 2024-05-12T20:48:22 Z shadow_sami Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 817 ms 52916 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 2 ms 8536 KB Output is correct
3 Correct 135 ms 48176 KB Output is correct
4 Correct 751 ms 52824 KB Output is correct
5 Correct 616 ms 34904 KB Output is correct
6 Correct 799 ms 52916 KB Output is correct
7 Correct 644 ms 43488 KB Output is correct
8 Correct 817 ms 52912 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 2 ms 8536 KB Output isn't correct
6 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 49708 KB Output is correct
6 Correct 71 ms 51924 KB Output is correct
7 Correct 36 ms 34392 KB Output is correct
8 Correct 69 ms 51904 KB Output is correct
9 Correct 7 ms 16984 KB Output is correct
10 Correct 72 ms 52084 KB Output is correct
11 Correct 71 ms 52908 KB Output is correct
12 Incorrect 73 ms 52688 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 170 ms 32376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 170 ms 32376 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 2 ms 8536 KB Output is correct
3 Correct 135 ms 48176 KB Output is correct
4 Correct 751 ms 52824 KB Output is correct
5 Correct 616 ms 34904 KB Output is correct
6 Correct 799 ms 52916 KB Output is correct
7 Correct 644 ms 43488 KB Output is correct
8 Correct 817 ms 52912 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8636 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Incorrect 2 ms 8536 KB Output isn't correct
14 Halted 0 ms 0 KB -