oj.uz

Submission #981114

# Submission time Handle Problem Language Result Execution time Memory
981114 2024-05-12T20:13:42 Z shadow_sami Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 863 ms 52920 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){
	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;
	ll nas = calc(tp2,tptp,0)+1;
	return nas;
}
 
// 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 8536 KB Output is correct
3 Correct 122 ms 48164 KB Output is correct
4 Correct 817 ms 52916 KB Output is correct
5 Correct 760 ms 35112 KB Output is correct
6 Correct 863 ms 52920 KB Output is correct
7 Correct 638 ms 43480 KB Output is correct
8 Correct 755 ms 52692 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 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 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 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 58 ms 49460 KB Output is correct
6 Correct 73 ms 52020 KB Output is correct
7 Correct 36 ms 34392 KB Output is correct
8 Correct 70 ms 51900 KB Output is correct
9 Correct 8 ms 16984 KB Output is correct
10 Correct 75 ms 52560 KB Output is correct
11 Correct 67 ms 52692 KB Output is correct
12 Correct 66 ms 52692 KB Output is correct
13 Incorrect 66 ms 52656 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8532 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 193 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 1 ms 8532 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 193 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 1 ms 8536 KB Output is correct
3 Correct 122 ms 48164 KB Output is correct
4 Correct 817 ms 52916 KB Output is correct
5 Correct 760 ms 35112 KB Output is correct
6 Correct 863 ms 52920 KB Output is correct
7 Correct 638 ms 43480 KB Output is correct
8 Correct 755 ms 52692 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 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 -