Easy 1 aiuto URGENTE

E’ da un po’ che sto provando questo problema ma non riesco proprio a capire cosa ci sia di sbagliato nel mio codice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


/*---------------------Treap Begin----------------*/

struct node
{
    int prior,size;
    ll val;//value stored in the array
    ll sum;//whatever info you want to maintain in segtree for each node
    ll lazy;//whatever lazy update you want to do
    struct node *l,*r;
};

typedef node* pnode;
int sz(pnode t)
{
    return t?t->size:0;
}
void upd_sz(pnode t)
{
    if(t)t->size=sz(t->l)+1+sz(t->r);
}
void lazy(pnode t)
{
    if(!t || !t->lazy)return;
    t->val+=t->lazy;//operation of lazy
    t->sum+=t->lazy*sz(t);
    if(t->l)t->l->lazy+=t->lazy;//propagate lazy
    if(t->r)t->r->lazy+=t->lazy;
    t->lazy=0;
}
void reset(pnode t)
{
    if(t)t->sum = t->val;//no need to reset lazy coz when we call this lazy would itself be propagated
}
void combine(pnode& t,pnode l,pnode r) //combining two ranges of segtree
{
    if(!l || !r)return void(t = l?l:r);
    t->sum = l->sum + r->sum;
}
void operation(pnode t) //operation of segtree
{
    if(!t)return;
    reset(t);//reset the value of current node assuming it now represents a single element of the array
    lazy(t->l);
    lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
    combine(t,t->l,t);
    combine(t,t,t->r);
}
void split(pnode t,pnode &l,pnode &r,int pos,int add=0)
{
    if(!t)return void(l=r=NULL);
    lazy(t);
    int curr_pos = add + sz(t->l);
    if(curr_pos<=pos)//element at pos goes to left subtree(l)
        split(t->r,t->r,r,pos,curr_pos+1),l=t;
    else
        split(t->l,l,t->l,pos,add),r=t;
    upd_sz(t);
    operation(t);
}
void merge(pnode &t,pnode l,pnode r)  //l->leftarray,r->rightarray,t->resulting array
{
    lazy(l);
    lazy(r);
    if(!l || !r) t = l?l:r;
    else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
    else    merge(r->l,l,r->l),t=r;
    upd_sz(t);
    operation(t);
}
pnode init(ll val)
{
    pnode ret = (pnode)malloc(sizeof(node));
    ret->prior=rand();
    ret->size=1;
    ret->val=val;
    ret->sum=val;
    ret->lazy=0;
    return ret;
}
ll range_query(pnode t,int l,int r) //[l,r]
{
    pnode L,mid,R;
    split(t,L,mid,l-1);
    split(mid,t,R,r-l);//note: r-l!!
    ll ans = t->sum;
    merge(mid,L,t);
    merge(t,mid,R);
    return ans;
}
void range_update(pnode t,int l,int r,int val) //[l,r]
{
    pnode L,mid,R;
    split(t,L,mid,l-1);
    split(mid,t,R,r-l);//note: r-l!!
    t->lazy+=val; //lazy_update
    merge(mid,L,t);
    merge(t,mid,R);
}

/*-----------------Treap End----------------------------*/


int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    pnode root=NULL;

    int n,m;
    sf(n);

    for(int i=1;i<=n;i++)
    {
        int a;
//        cin>>a;
        sf(a);
        merge(root,root,init(a));
    }

    cout << root->sum << endl;

    return 0;
}

@veluca @bortoz @dario2994 potete darmi una mano?

3 Mi Piace

Ciao. Credo che il problema sia che stai usando un treap al posto di un mucchialbero. Buona giornata

5 Mi Piace

Hai ragione! Ho incluso <olita.h>, riscritto il codice e funziona!

4 Mi Piace


Da quando avete iniziato a memare in maniera seriale sul forum non mi perdo una sola mail di riepilogo.

4 Mi Piace

Ciao, non capisco cosa ci sia da “memare” nella soluzione che ho proposto. Capisco che non sia efficiente come un treap di dsu ma purtroppo ho troppo lo skill issue e non lo so implementare, se tu sei in grado me lo potresti spiegare?

1 Mi Piace

Non so cosa ti mandino alle EGOI a fare se non sai nemmeno che easy 1 si risolve con Dijkstra.

@marco_pellero può spiegarti tutto per la modica cifra di 5 euro l’ora.
Preparati un centone perché in meno di una giornata l’implementazione non la capisce nemmeno chi l’ha scritta.

La prossima volta mandiamo lui alle EGOI, altro che Franca e Alessandra che sembrano non essere nemmeno in grado di stabilire la parità di un numero in tempo esponenziale.

1 Mi Piace

Ciao, essendo questo un problema base, occorre ritornare alle basi stesse dell’informatica: il linguaggio macchina!
La macchina che prendiamo in considerazione è una “macchina printf” molto semplice. Ha 10 registri a 16 bit, con il seguente layout:

| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
| ip | it | in | ou | gp | gp | gp | gp | gp | gp !

ip = instruction pointer
it = interrupt register
in = input register
out = output register  
gp = general purpose registers

Il programma non è altro che un array di format strings! Infatti la macchina esegue ciclicamente una chiamata a printf prendendo come format string l’istruzione a cui punta l’ip e come parametri i valori e i puntatori di tutti i registri (più una stringa vuota). Un stringa nulla equivale a un’istruzione di halt.
Inoltre la macchina possiede capacità basilari di I/O: quando it è settato 1 la macchina interrompe il normale ciclo aspettando che venga dato in input un intero, che viene salvato in in.
Invece, quando it è settato a 2, la macchina interrompe l’esecuzione e fornisce in output il valore presente in out.
Questa semplice macchina ci permette di risolvere agevolemente il problema senza usare i mucchialberi: lascio un esempio di implementazione.

0x00: "%1$60000s%15$hn"
0x01: " %13$hn"
0x02: "%1$*4$s%1$65535s%21$hn"
0x03: " %13$hn"                  
0x04: "%1$*4$s%17$hn"             
0x05: "%1$*5$s%19$hn"         
0x06: "%7$hu%1$*2$s%12$hn"      
0x07: "%1$12s%12$hn"             
0x08: "%1$12s%12$hn"             
0x09: "%1$12s%12$hn"            
0x0A: "%1$12s%12$hn"          
0x0B: "%1$19s%12$hn"          
0x0C: ""               
0x0D: "%9$hu%1$*2$s%12$hn"       
0x0E: "%1$18s%12$hn"             
0x0F: "%1$18s%12$hn"             
0x10: "%1$18s%12$hn"           
0x11: "%1$18s%12$hn"             
0x12: "%1$26s%12$hn"           
0x13: "%1$21s%12$hn"           
0x14: "%1$*4$s%15$n"           
0x15: "%1$26s%12$n"              
0x16: " %1$*7$s%17$hn"            
0x17: " %1$*9$s%19$hn"           
0x18: "%1$5s%12$hn"              
0x19: NULL                      
0x1A: NULL                      
0x1B: "%1$*11$s%1$65535s%21$hn" 
0x1C: "%11$hu%1$*2$s%12$hn"    
0x1D: "%1$2s%12$hn"       
0x1E: "%1$2s%12$hn"            
0x1F: "%1$2s%12$hn"             
0x20: "%1$2s%12$hn"               
0x21: "%1$2s%12$hn"               
0x22: "  %13$hn"              
0x23: ""      
0x24: NULL

Sicuramente avrai modo di impratichirti con questa tecnica alle EGOI.

6 Mi Piace

Grazie, mi hai dato questo consiglio proprio prima di due ore di aereo per arrivare alle EGOI, passerò queste ore a impratichirmi!

1 Mi Piace