Submission #1213452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213452		Malix	Secret (JOI14_secret)	C++20	0 / 100	343 ms	8636 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vii mp;
vi a;
int n;
set<pi> st;

void solve(int l,int r){
  if(l==r)return;
  if(l+1==r){
    mp[l][r]=Secret(a[l],a[r]);
    return;
  }
  int m=(l+r)/2;
  solve(l,m);
  solve(m+1,r);
  int c=a[m];
  for(int i=m-1;i>=l;i--){
    if(st.count({i,m})==0){
      mp[i][m]=Secret(a[i],c);
      c=mp[i][m];
      st.insert({i,m});
    }
    else c=mp[i][m];
  }
  c=a[m+1];
  REP(i,m+2,r+1){
    if(st.count({m+1,i})==0){
     mp[m+1][i]=Secret(c,a[i]);
      c=mp[m+1][i];
      st.insert({m+1,i});
    }
    else c=mp[m+1][i];
  }
}

void Init(int N, int A[]) {
  n=N;
  a.resize(n);
  mp.resize(n,vi(n,-1));
  REP(i,0,n){
    a[i]=A[i];
    mp[i][i]=A[i];
    st.insert({i,i});
  }
  solve(0,n-1);
}

int Query(int L, int R) {
  auto it=st.lower_bound({L+1,0});
  it=prev(it);
  int m=it->S;
  return Secret(mp[L][m],mp[m+1][R]);
}

• Subtask 1: 0 / 100