oj.uz

Submission #56572

# Submission time Handle Problem Language Result Execution time Memory
56572 2018-07-11T18:49:19 Z Mamnoon_Siam Secret (JOI14_secret) C++17
100 / 100
 724 ms 5468 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 2804 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 209 ms 2920 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 191 ms 2996 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 678 ms 5252 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 642 ms 5452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 628 ms 5452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 724 ms 5452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 600 ms 5452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 691 ms 5452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 605 ms 5468 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1