oj.uz

Submission #908878

# Submission time Handle Problem Language Result Execution time Memory
908878 2024-01-17T01:05:21 Z vjudge1 Secret (JOI14_secret) C++17
0 / 100
 384 ms 4432 KB 
#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){
            if(!cola.empty()){
                pos=cola.back().pos;
                ini=cola.back().ini;
                fin=cola.back().fin;
                cola.pop_back();
            }
            else{
                break;
            }
            continue;
        }
        if(L <= ini && R >= fin-1){
            op.push_back(pos);
            if(!cola.empty()){
                pos=cola.back().pos;
                ini=cola.back().ini;
                fin=cola.back().fin;
                cola.pop_back();
            }
            else{
                break;
            }
            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;
         if(!cola.empty()){
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
        }
        else{
            break;
        }
    }
    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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 3700 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 307655478.
2 Incorrect 97 ms 3664 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 843233288.
3 Incorrect 97 ms 3668 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 213119272.
4 Incorrect 369 ms 4376 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 836796525.
5 Incorrect 360 ms 4428 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 799693888.
6 Incorrect 367 ms 4328 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 206870645.
7 Incorrect 379 ms 4432 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 613594163.
8 Incorrect 365 ms 4324 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 202667392.
9 Incorrect 363 ms 4432 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 30936558.
10 Incorrect 384 ms 4320 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 1084228.