제출 #1257961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257961		xardkodych	Gap (APIO16_gap)	C++20	8.18 / 100	222 ms	32596 KiB

gap

// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;

void MinMax(long long s, long long t, long long *mn, long long *mx);
const int INF = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

class solver {
public:
  int Rand(int l, int r) {
    return l + rnd() % (r - l + 1);
  }
  map<pii, pii> mem;
  pii query(int a, int b) {
    if (mem.contains({a,b}))
      return mem[{a,b}];
    if (a > b)
      return mem[{a,b}]={-1, -1};
    int u, v;
    MinMax(a, b, &u, &v);
    return mem[{a,b}]={u, v};
  }
  int answer;
  int f(int l, int r) {
    if (l > r)
      return 0;
    if (auto [u,v]=query(l,r); u == v || u == -1)
      return 0;
    int mid = Rand(l, r);
    int res = 0;
    res = max(res, f(l, mid));
    res = max(res, f(mid+1, r));
    int left = query(l, mid).S;
    int right = query(mid+1, r).F;
    if (left != -1 && right != -1) {
      res = max(res, right - left);
    }
    return res;
  }
  solver(int t, int n) {
    answer = f(0, INF);
  }
};

int findGap(int32_t t, int32_t n) {
  if (t == 1) {

  }
  if (t == 2) {
    solver sol(t, n);
    return sol.answer;
  }
}

#undef int

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'long long int findGap(int32_t, int32_t)':
gap.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

• Subtask 1: 0 / 30
• Subtask 2: 8.1764 / 70