oj.uz

Submission #961042

# Submission time Handle Problem Language Result Execution time Memory
961042 2024-04-11T12:35:25 Z Pring Secret (JOI14_secret) C++17
100 / 100
 458 ms 5012 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else 
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
	const int MXN = 1005;
	int n, a[MXN], d[MXN];
	map<pii, int> M;

	struct SMG {
		pii val[MXN * 2];
		void build() {
			FOR(i, 0, n) val[i + n] = mp(d[i], i);
			for (int i = n - 1; i; i--) {
				val[i] = min(val[i << 1], val[(i << 1) | 1]);
			}
		}
		pii query(int l, int r) {
			pii x = mp(INT_MAX, -1);
			for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
				if (l & 1) x = min(x, val[l++]);
				if (r & 1) x = min(x, val[--r]);
			}
			return x;
		}
	} smg;

	void SUF(int l, int r) {
		int x = a[r - 1];
		for (int i = r - 2; i >= l; i--) {
			x = Secret(a[i], x);
			M[mp(i, r - 1)] = x;
		}
	}
	void PRE(int l, int r) {
		int x = a[l];
		for (int i = l + 1; i < r; i++) {
			x = Secret(x, a[i]);
			M[mp(l, i)] = x;
		}
	}

	void build(int l, int r, int dep) {
		if (l + 1 == r) return;
		int mid = (l + r) >> 1;
		d[mid] = dep;
		SUF(l, mid);
		PRE(mid, r);
		build(l, mid, dep + 1);
		build(mid, r, dep + 1);
	}

	void init() {
		FOR(i, 0, n) M[mp(i, i)] = a[i];
		build(0, n, 0);
		smg.build();
	}

	int query(int l, int r) {
		if (l == r) return a[l];
		int bnd = smg.query(l + 1, r + 1).sc;
		debug(bnd);
		return Secret(M[mp(l, bnd - 1)], M[mp(bnd, r)]);
	}
}

void Init(int N, int A[]) {
	::n = N;
	FOR(i, 0, n) a[i] = A[i];
	init();
}

int Query(int l, int r) {
	return query(l, r);
}

Compilation message

secret.cpp: In function 'int {anonymous}::query(int, int)':
secret.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
secret.cpp:79:3: note: in expansion of macro 'debug'
   79 |   debug(bnd);
      |   ^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2808 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 113 ms 2900 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 112 ms 2824 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 390 ms 4912 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 458 ms 5012 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 388 ms 4860 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 388 ms 4984 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 382 ms 4804 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 396 ms 5008 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 379 ms 4952 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1