oj.uz

Submission #908868

# Submission time Handle Problem Language Result Execution time Memory
908868 2024-01-17T00:50:35 Z vjudge1 Secret (JOI14_secret) C++17
0 / 100
 366 ms 4436 KB 
#include <vector>
using namespace std;//

#include "secret.h"


//int A[10000];//////

int tree[4005];

/*void arbol(int pos, int ini, int fin){
    if(fin-ini==2){
        tree[pos]=Secret(A[ini], A[fin-1]);
        arbol(pos*2, ini, ini+1);
        arbol(pos*2+1, ini+1, fin);
        return;
    }
    if(fin-ini==1){
        tree[pos]=A[ini];
        return;
    }
    if(ini == fin)
        return;
    arbol(pos*2, ini, (ini+fin)/2);
    arbol(pos*2+1, (ini+fin)/2, fin);
    tree[pos]=Secret(tree[pos*2], tree[pos*2+1]);
}*/

struct estado{
  int pos;
  int ini;
  int fin;
};

int tam;

void Init(int N, int A[]){
    tam=N;
    for(int c=1; c <=4*N+1; c++){
        tree[c]=-1;
    }
    int ini=1;
    int fin=N+1;
    int pos=1;
    vector <estado> cola;
    while(1){
        if(fin-ini==2){
            tree[pos]=Secret(A[ini], A[fin-1]);
            tree[pos*2]=A[ini];
            tree[pos*2+1]=A[ini+1];
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(fin-ini==1){
            tree[pos]=A[ini];
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(ini == fin){
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(tree[pos*2]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            fin=(ini+fin)/2;
            continue;
        }
        if(tree[pos*2+1]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            pos++;
            ini=(ini+fin)/2;
            continue;
        }
        tree[pos]=Secret(tree[pos*2], tree[pos*2+1]);
        if(pos == 1)
            break;
        pos=cola.back().pos;
        ini=cola.back().ini;
        fin=cola.back().fin;
        cola.pop_back();
        continue;
    }
    /*for(int c=1; c <=4*N+1; c++){
        cout << tree[c] << " ";
    }*/
}
    
int Query(int L, int R){
    L++;
    R++;
    vector <int> op;
    int vis[40005];
    for(int c=1; c <=40002; c++){
        vis[c]=-1;
    }
    int ini=1;
    int fin=tam+1;
    int pos=1;
    vector <estado> cola;
    while(1){
        vis[pos]++;
        if(ini > R || fin <= L){
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(L <= ini && R >= fin-1){
            op.push_back(pos);
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(vis[pos*2]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            fin=(ini+fin)/2;
            continue;
        }
        if(vis[pos*2+1]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            pos++;
            ini=(ini+fin)/2;
            continue;
        }
        if(pos==1)
            break;
        pos=cola.back().pos;
        ini=cola.back().ini;
        fin=cola.back().fin;
        cola.pop_back();
    }
    int resp=tree[op.back()];
    op.pop_back();
    while(!op.empty()){
        resp=Secret(resp, tree[op.back()]);
        op.pop_back();
    }
    return resp;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 3664 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 319888796.
2 Incorrect 98 ms 3504 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 74449256.
3 Incorrect 99 ms 3656 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 420878626.
4 Incorrect 361 ms 4332 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 823361617.
5 Incorrect 364 ms 4436 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 420140296.
6 Incorrect 366 ms 4324 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 206870645.
7 Incorrect 364 ms 4320 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 260120643.
8 Incorrect 365 ms 4436 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 770092496.
9 Incorrect 364 ms 4324 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 290717864.
10 Incorrect 362 ms 4432 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 543974401.