Submission #56572

#	Time	Username	Problem	Language	Result	Execution time	Memory
56572		Mamnoon_Siam	Secret (JOI14_secret)	C++17	100 / 100	724 ms	5468 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int op(int x, int y) {
	return Secret(x, y);
}

struct Tree {
	vector<int> v;
	vector<map<int, int>> pre, suf;
	Tree() {}
	Tree(vector<int> &vec) {
		v = vec;
		pre.resize(v.size() * 4);
		suf.resize(v.size() * 4);
		build(1, 0, v.size() - 1);
	}
	void build(int u, int b, int e) {
		if(b == e) {
			suf[u][b] = v[b], pre[u][b] = v[b];
			return;
		} int mid = b + e >> 1;
		build(u << 1, b, mid);
		build(u << 1 | 1, mid + 1, e);
		if(b == 0 and e == v.size() - 1) return ;
		if(u % 2 == 1) {
			pre[u][b] = v[b];
			for(int i = b + 1; i <= e; i++) {
				pre[u][i] = op(pre[u][i - 1], v[i]);
			}
		}
		if(u % 2 == 0) {
			suf[u][e] = v[e];
			for(int i = e - 1; i >= b; i--) {
				suf[u][i] = op(v[i], suf[u][i + 1]);
			}
		}
	}
	int query(int u, int b, int e, int i, int j) {
		// cout << "b = " << b << ", e = " << e << endl;
		int mid = b + e >> 1;
		if(b <= i and j <= e and i <= mid and mid + 1 <= j) {
			return op(suf[u << 1][i], pre[u << 1 | 1][j]);
		} if(i >= mid + 1) { // right
			return query(u << 1 | 1, mid + 1, e, i, j);
		} else { // left
			return query(u << 1, b, mid, i, j);
		}
	}
	int query(int l, int r) {
		if(l == r) return v[l];
		if(l == r + 1) return op(v[l], v[r]);
		// cout << "Query = " << l << ", " << r << endl;
		return query(1, 0, v.size() - 1, l, r);
	}
};

Tree ds;

void Init(int N, int A[]) {
	vector<int> v(A, A + N);
	ds = Tree(v);
}

int Query(int L, int R) {
	return ds.query(L, R);
}

Compilation message (stderr)

secret.cpp: In member function 'void Tree::build(int, int, int)':
secret.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   } int mid = b + e >> 1;
               ~~^~~
secret.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(b == 0 and e == v.size() - 1) return ;
                 ~~^~~~~~~~~~~~~~~
secret.cpp: In member function 'int Tree::query(int, int, int, int, int)':
secret.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = b + e >> 1;
             ~~^~~

• Subtask 1: 100 / 100