Submission #235771

#TimeUsernameProblemLanguageResultExecution timeMemory
235771BlagojceSecret (JOI14_secret)C++11
30 / 100
556 ms4732 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define pb push_back #define st first #define nd second #define pq priority_queue #define all(x) begin(x), end(x) #include <time.h> #include <cmath> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const ll inf = 1e18; const ll mod = 1000000007; const ld eps = 1e-13; const ld pi = 3.14159265359; mt19937 _rand(time(NULL)); clock_t timer = clock(); const int mxn = 5e5 + 5; #include "secret.h" /* int Secret(int x, int y){ return x + y; }*/ //int seg[10000]; int n; int a[1001];/* void build(int k, int l, int r){ if(l == r){ seg[k] = a[l]; return; } int mid = (l + r) / 2; build(k * 2, l, mid); build(k * 2 + 1, mid + 1, r); seg[k] = Secret(seg[k * 2], seg[k * 2 + 1]); } vector<int> v; void query(int k, int l, int r, int x, int y){ if(y < l || r < x) return; if(x <= l && r <= y){ v.pb(seg[k]); return; } int mid = (l + r) / 2; query(k * 2, l, mid, x, y); query(k * 2 + 1, mid + 1, r, x, y); }*/ int sparse[10001][10]; void Init(int N, int A[]) { n = N; fr(i, 0, N){ a[i] = A[i]; sparse[i][0] = a[i]; } fr(i, 1, 10){ for(int j = 0; j + (1 << i) - 1 < n; j ++){ sparse[j][i] = Secret(sparse[j][i - 1], sparse[j + (1<<(i-1))][i - 1]); } } //build(1, 0, n-1); } int Query(int L, int R){ int len = (R - L + 1); int ans = -1; for(int i = 9; i >= 0; i --){ if(len & (1 << i)){ if(ans == -1){ ans = sparse[L][i]; } else{ ans = Secret(ans, sparse[L][i]); } L += (1 << i); } } return ans; /*v.clear(); query(1, 0, n - 1, L, R); int ans = v[0]; fr(i, 1, (int)v.size()){ ans = Secret(ans, v[i]); } return ans;*/ } /* int main(){ int N; cin >> N; int A[N]; fr(i, 0, N){ cin >> A[i]; } Init(N, A); int Q; cin >> Q; while(Q --){ int L, R; cin >> L >> R; Query(L, R); } }*/
#Verdict Execution timeMemoryGrader output
Fetching results...