Submission #1207610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207610		ricardsjansons	Secret (JOI14_secret)	C++20	30 / 100	356 ms	5252 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int N=1<<10;

vector<int>segt(N*2,-1);

map<pair<int,int>,int>hintmem;

int hint(int x,int y){
    if(hintmem.count({x,y})){
        return hintmem[{x,y}];
    }
    hintmem[{x,y}]=Secret(x,y);
    return hintmem[{x,y}];
}

void upd(int i,int x){
    i+=N;
    segt[i]=x;
    for(i/=2;i;i/=2){
        if(segt[i*2]<0||segt[i*2+1]<0){
            break;
        }
        segt[i]=hint(segt[i*2],segt[i*2+1]);
    }
}

void Init(int n, int a[]) {
    for(int i=0;i<n;i++){
        upd(i,a[i]);
    }
}

int hintsf(vector<int>v){
    int res=v.back();
    for(int i=v.size()-2;i>=0;i--){
        res=hint(v[i],res);
    }
    return res;
}

int hintpf(vector<int>v){
    int res=v.front();
    for(int i=1;i<v.size();i++){
        res=hint(res,v[i]);
    }
    return res;
}


int Query(int l, int r) {
    //cout<<"!"<<endl;
    l+=N;
    r+=N;
    vector<int>vl,vr;
    while(l<=r){
        if(l%2==1){
            vl.push_back(segt[l++]);
        }
        if(r%2==0){
            vr.push_back(segt[r--]);
        }
        l/=2;
        r/=2;
    }
    reverse(vr.begin(),vr.end());
    int res;
    if(vl.empty()){
        res=hintpf(vr);
    }else if(vr.empty()){
        res=hintsf(vl);
    }else{
        res=hint(hintsf(vl),hintpf(vr));
    }
    return res;
}

• Subtask 1: 30 / 100