oj.uz

Submission #314472

# Submission time Handle Problem Language Result Execution time Memory
314472 2020-10-20T02:49:24 Z jc713 Secret (JOI14_secret) C++17
100 / 100
 511 ms 4496 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,min(l, orig),min(m, orig)){
			if(prod == id)
				stor[i][ind] = prod = a[i];
			else
				stor[i][ind] = prod = comb(a[i],prod);
		}
		prod = id; FOR(i,min(m, orig),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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 2428 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 Correct 143 ms 2424 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 503 ms 4496 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 501 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 508 ms 4472 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 503 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 501 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 511 ms 4472 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 504 ms 4472 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1