Submission #908872

#	Time	Username	Problem	Language	Result	Execution time	Memory
908872		vjudge1	Secret (JOI14_secret)	C++17	0 / 100	374 ms	4832 KiB

secret

#include <vector>
#include <algorithm>
using namespace std;//

#include "secret.h"

int tree[4005];

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();
    }
    sort(op.begin(), op.end());
    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 / 100