oj.uz

Submission #314458

# Submission time Handle Problem Language Result Execution time Memory
314458 2020-10-20T01:07:56 Z jc713 Secret (JOI14_secret) C++17
0 / 100
 500 ms 8696 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){
				assert(0 == 1);
				stor[i][ind] = prod = a[i];
			}
			else
				stor[i][ind] = prod = comb(a[i],prod);
		}
		prod = id; FOR(i,m,min(r, orig)){
			if(prod == id){
				assert(0 == 1);
				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[i] = 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 Runtime error 131 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 132 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 134 ms 4760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 489 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 491 ms 8616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 490 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 500 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 492 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 494 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 491 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)