oj.uz

Submission #1099562

# Submission time Handle Problem Language Result Execution time Memory
1099562 2024-10-11T16:12:31 Z dzhoz0 Secret (JOI14_secret) C++17
0 / 100
 330 ms 8888 KB 
/*
    ghmt the cutie :3
          UwU
*/

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

#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
template<typename T, int SZ> struct RangeQuery {
	int n;
	T stor[SZ][32-__builtin_clz(SZ)], id = 1;
	vector<T> a;
	T comb (T a, T b) { return Secret(a, b); } // associative operation
	void fill(int l, int r, int ind) {
		if (ind < 0) return;
		int m = (l+r)/2;
		T prod = id; ROF(i,l,m) stor[i][ind] = prod = comb(a[i],prod);
		prod = id; FOR(i,m,r) stor[i][ind] = prod = comb(prod,a[i]);
		fill(l,m,ind-1); fill(m,r,ind-1);
	}
	void init() {
		n = 1; while ((1<<n) < a.size()) ++n;
		a.resize(1<<n); fill(0,(1<<n),n-1);
	}
	T query(int l, int r) {
		if (l == r) return a[l];
		int t = 31-__builtin_clz(r^l);
		return comb(stor[l][t],stor[r][t]);
	}
};

const int MAXN = 1000;

RangeQuery<long long, MAXN + 5> rq;
void Init(int n, int a[]) {
    for(int i = 0; i < n; i++) rq.a.push_back(a[i]);
    rq.init();
}

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

Compilation message

secret.cpp: In instantiation of 'void RangeQuery<T, SZ>::init() [with T = long long int; int SZ = 1005]':
secret.cpp:48:13:   required from here
secret.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   n = 1; while ((1<<n) < a.size()) ++n;
      |                 ~~~~~~~^~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 2384 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 591660520.
2 Incorrect 93 ms 2608 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 116629953.
3 Runtime error 82 ms 4832 KB Execution killed with signal 11
4 Runtime error 305 ms 8712 KB Execution killed with signal 11
5 Runtime error 307 ms 8888 KB Execution killed with signal 11
6 Runtime error 330 ms 8784 KB Execution killed with signal 11
7 Runtime error 308 ms 8784 KB Execution killed with signal 11
8 Runtime error 311 ms 8716 KB Execution killed with signal 11
9 Runtime error 314 ms 8728 KB Execution killed with signal 11
10 Runtime error 319 ms 8692 KB Execution killed with signal 11