#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);
}
| # |
결과 |
실행 시간 |
메모리 |
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) |
