Sto cercando di risolvere muraglia, ma mi esce execution timed out per la maggior parte dei subtask, il problema è che superano tutti i 4 secondi, io pensavo che a 1 secondo si fermasse direttamente, quindi non capisco se c’è qualche errore strano nel mio programma. Qualcuno potrebbe aiutarmi a controllarlo e magari anche a migliorarlo grazie.
Sto cercando di risolverlo con un segment tree. Questo è il programma:
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <vector>
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l+r>>1)
using namespace std;
const int T = 10e6;
long long tree[4*T], c=0, A;
vector<long long> B;
void build(int o,int l,int r, vector<int> H);
void cambia(int x, int h);
int get(int o, int l, int r, int x, int a_x);
pair<int, int> chiedi(int x);
int get1(int o, int l, int r, int x, int a_x);
void cambia1(int o,int l,int r,int x,int h);
int get3(int o, int l, int r, int x);
pair<int, int> chiedi(int x){
pair<int,int> ans;
if(x<1){
ans.second=get3(1,0,A-1,B[x]);
ans.first=0;
}
else{
ans.first=get1(1,0,A-1,x,B[x]);
ans.second=get(1,0,A-1,x,B[x]);
}
if(ans.second==0)
ans.second=A-1;
return ans;
}
void cambia(int x, int h){
B[x]=h;
cambia1(1,0,A-1,x,h);
}
void inizializza(int N, vector<int> H){
build(1,0,N-1,H);
A=N;
for(int i=0;i<N;i++){
B.push_back(H[i]);
}
}
void cambia1(int o,int l,int r,int x,int h){
/*if(r<x||l>x) return;
if(l==r&&l==x)
{
tree[o]=h;
return;
}
cambia1(ls,l,mid,x,h);
cambia1(rs,mid+1,r,x,h);
tree[o] = max(tree[ls],tree[rs]);*/
if(l==r) {
tree[o]=h;return ;
}
if(x<=mid) cambia1(ls,l,mid,x,h);
else cambia1(rs,mid+1,r,x,h);
tree[o] = max(tree[ls],tree[rs]);
}
void build(int o,int l,int r, vector<int> H){
if(l==r){
tree[o]=H[c];
c++;
return;
}
build(ls,l,mid,H);
build(rs,mid+1,r,H);
tree[o] = max(tree[ls],tree[rs]);
}
int get3(int o, int l, int r, int x) {
if (l == r) return l;
return tree[ls] > x ? get3(ls, l, mid, x) : get3(rs, mid+1, r, x);
}
int get(int o, int l, int r, int x, int a_x){
if(tree[o]<=a_x)
return 0;
if(r<=x)
return 0;
if(l==r)
return l;
int ans=get(ls,l,mid,x,a_x);
return ans
?ans
:get(rs,mid+1,r,x,a_x);
}
int get1(int o, int l, int r, int x, int a_x){
if(tree[o]<=a_x)
return 0;
if(l>=x)
return 0;
if(l==r)
return l;
int ans=get1(rs,mid+1,r,x,a_x);
return ans
?ans
:get1(ls,l,mid,x,a_x);
}
Un’altra domanda, ho visto che alcune persone usa no bbst o stack, se il mio programma non può essere migliorato potreste darmi uno spunto su come usare bbst o stack?