oj.uz

Submission #314463

# Submission time Handle Problem Language Result Execution time Memory
314463 2020-10-20T01:57:36 Z jc713 Secret (JOI14_secret) C++17
0 / 100
 515 ms 8824 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
				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 Correct 144 ms 2516 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2424 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Runtime error 140 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 502 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 503 ms 8816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 504 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 507 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 515 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 501 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 506 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)