oj.uz

Submission #297522

# Submission time Handle Problem Language Result Execution time Memory
297522 2020-09-11T15:42:13 Z penguinhacker Secret (JOI14_secret) C++17
0 / 100
 527 ms 4600 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

#define ll long long
#define ar array

/*int Secret(int a, int b) {
	return min(a, b);
}*/

template<class T> struct range_query {
	int n;
	vector<T> a;
	vector<vector<T>> st;
	void init(vector<T> _a) {
		a = _a;
		n = a.size();
		int x = 0;
		while((1 << x) < n) {
			++x;
		}
		a.resize(1 << x);
		st.assign(1 << x, vector<T>(x));
		build(0, (1 << x) - 1, x - 1);
	}
	T combine(T a, T b) {
		return Secret(a, b);
	}
	void build(int l, int r, int lev) {
		if (lev < 0) {
			return;
		}
		int mid = (l + r) >> 1;
		st[mid][lev] = a[mid];
		for (int i = mid - 1; i >= l; --i) {
			st[i][lev] = combine(st[i + 1][lev], a[i]);
		}
		if (r > mid) {
			st[mid + 1][lev] = a[mid + 1];
			for (int i = mid + 2; i <= r; ++i) {
				st[i][lev] = combine(st[i -1][lev], a[i]);
			}
		}
		build(l, mid, lev - 1);
		build(mid + 1, r, lev - 1);
	}
	T qry(int l, int r) {
		assert(l <= r);
		if (l == r) {
			return a[l];
		}
		int x = 31 - __builtin_clz(l ^ r);
		return combine(st[l][x], st[r][x]);
	}
};

range_query<int> rq;

void Init(int N, int A[]) {
	vector<int> a(A, A + N);
	rq.init(a);
}

int Query(int L, int R) {
	return rq.qry(L, R);
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	

	return 0;
}*/

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 2552 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 150 ms 2536 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 137 ms 2552 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 162768982.
4 Incorrect 506 ms 4472 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 546373765.
5 Incorrect 498 ms 4600 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 707448136.
6 Incorrect 507 ms 4600 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 302576192.
7 Incorrect 527 ms 4432 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 54559803.
8 Incorrect 518 ms 4600 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 822146056.
9 Incorrect 509 ms 4600 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 408296780.
10 Incorrect 524 ms 4600 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 67347979.