제출 #1164055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164055		dombly	비밀 (JOI14_secret)	C++20	100 / 100	345 ms	5520 KiB

secret

#define f first
#define s second
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
map<pair<int,int> ,int> mp;
    int nn;
struct tree{
    int seg[4*N];
    int *a;
    void build(int cur,int l,int r) {
        if(l==r)mp[{l,l}]=seg[cur] = a[l];
        else {
            int mid = (l+r)/2;
            build(cur*2,l,mid);
            build(cur*2+1,mid+1,r);
            mp[{l,r}]=seg[cur]=Secret(seg[cur*2],seg[cur*2+1]);
        }
    }
    void process(int cur,int l,int r) {
        if(abs(l-r) < 2) return;
        int mid = (l+r)/2;
        process(cur*2,l,mid);process(cur*2+1,mid+1,r);
        // left side
        int cnt = seg[cur*2];
        if(l!=0){
            for(int i = mid+1;i<r;i++){
                if(!mp[{l,i}])mp[{l,i}]=Secret(cnt,a[i]);
                cnt = mp[{l,i}];
            }
        }
        cnt = seg[cur*2+1];
        if(r!=nn-1){
            for(int i = mid;i>l;i--){
                if(!mp[{i,r}])mp[{i,r}]=Secret(a[i],cnt);
                cnt = mp[{i,r}];
            }
        }
    }
    int qry(int cur,int ll,int rr,int l = 0,int r = nn-1) {
        if(l > rr || r < ll) return -1;
        int res;
        int bl = max(ll,l),br = min(rr,r);
        if(mp[{bl,br}])res = mp[{bl,br}];
        else {
            int mid = (l + r) / 2;
            int a = qry(cur*2,ll,rr,l,mid), b = qry(cur*2+1,ll,rr,mid+1,r);
            if(a==-1 || b==-1)res = (a==-1?b:a);
            else res = Secret(a,b);
        }
        // cout << l << " " << r << " " << res << "\n";
        return res;
    }
}t;

void Init(int n, int a[]) {
    t.a=a;
    nn=n;
    t.build(1,0,n-1);
    t.process(1,0,n-1);

    // for(auto a : mp)cout<<a.f.f<<" " << a.f.s << " " << a.s << '\n';
}

int Query(int l, int r) {
    return t.qry(1,l,r);
}
/*


g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp



*/

• Subtask 1: 100 / 100