oj.uz

Submission #197876

# Submission time Handle Problem Language Result Execution time Memory
197876 2020-01-24T01:17:16 Z Malomalomalomalo Secret (JOI14_secret) C++14
0 / 100
 589 ms 4600 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> a(1000 + 5);
int n;

struct node{
	node * c[2] = {nullptr, nullptr};
	int m = 0,l,r;
	vector<int> val;
	void init(int l, int r){
		this->l = l;this->r = r;	
		m = (r+l)/2;
		val = vector<int>(r-l+1);
		val[m-l] = a[m];
		for(int i = m-1;i >= l; --i){
			val[i-l] = Secret(a[i],val[i+1-l]);
		}
		val[m+1-l] = a[m+1];
		for(int i = m+2;i <= r; ++i){
			val[i-l] = Secret(a[i],val[i-1-l]);
		}
		if(r-l+1 >= 5){
			c[0] = new node();
			c[1] = new node();
			if(m-l >= 2)c[0]->init(l,m-1);
			if(r-(m+1) >= 2)c[1]->init(m+2,r);
		}
	}
	int query(int L, int R){
		if(R <= m-1){
			return c[0]->query(L,R);
		}
		else if(L >= m+2){
			return c[1]->query(L,R);
		}
		else{
			assert(l <= L && r >= R);
			if(R == m)return val[L-l];
			else if(L == m + 1)return val[R-l];
			else return Secret(val[L-l],val[R-l]);
		}
	}
} root;

void Init(int N, int A[]) {
	n = N;
	for(int i = 0;i < n; ++i)a[i] = A[i];
	root.init(0,n-1);
}

int Query(int L, int R) {
  return (L == R ? a[L] :root.query(L,R));
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 2524 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 809782271.
2 Incorrect 158 ms 2424 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 68749376.
3 Incorrect 158 ms 2440 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 136349820.
4 Incorrect 581 ms 4452 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 650789536.
5 Incorrect 579 ms 4344 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 16813134.
6 Incorrect 584 ms 4460 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 722663411.
7 Incorrect 585 ms 4408 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 687550570.
8 Incorrect 586 ms 4444 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 145923264.
9 Incorrect 585 ms 4480 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 18757135.
10 Incorrect 589 ms 4600 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 70590726.