oj.uz

Submission #314469

# Submission time Handle Problem Language Result Execution time Memory
314469 2020-10-20T02:41:54 Z jc713 Secret (JOI14_secret) C++17
0 / 100
 505 ms 8708 KB 
#include "secret.h"

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

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

// loops
#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)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

// helper funcs
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

template<class T, int SZ> struct RangeQuery {
	int n; int orig;
	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){
			if(prod == id)
				stor[i][ind] = prod = a[i];
			else{
				if(i == (l + m) / 2)
					stor[i][ind] = prod = stor[m - 1][ind - 1];
				else
					stor[i][ind] = prod = comb(a[i],prod);
			}
		}
		prod = id; FOR(i,m,min(r, orig)){
			if(prod == id)
				stor[i][ind] = prod = a[i];
			else
				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) < sz(a)) n++;
		a.rsz(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]);
	}
};

RangeQuery<int, 1000> RQ;

void Init(int N, int A[]) {
	RQ.orig = N;
	F0R(i, N)
		RQ.a.pb(A[i]);
	RQ.init();
}

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

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 2424 KB Wrong Answer: Query(51, 467) - expected : 268834016, actual : 591881858.
2 Incorrect 133 ms 2460 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 597766465.
3 Runtime error 137 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 501 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 500 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 500 ms 8632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 505 ms 8708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 501 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 497 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 501 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)