#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
// int Secret(int X, int Y)
// ll COUNT = 0;
// int Secret (int X, int Y) {
// COUNT++;
// // if (X > 1E9-Y) return 1E9;
// return (X+Y)%10000000;
// }
// struct Segment {
// int l, r, id;
// Segment (int l, int r, int id): l(l), r(r), id(id) {}
// };
// int dp[1005][1005];
// bool vis[1005][1005];
// vector <Segment> nivs[12];
struct SegTree {
vector <int> tree;
int n;
void build (vector <int> ve, int l, int r, int id, int niv) {
// nivs[niv].push_back(Segment(l, r, id));
if (l==r) {
tree[id] = ve[l];
// dp[l][r] = tree[id];
// vis[l][r] = true;
return;
}
int mid = (l+r)>>1;
build(ve, l, mid, 2*id+1, niv+1);
build(ve, mid+1, r, 2*id+2, niv+1);
tree[id] = Secret(tree[2*id+1], tree[2*id+2]);
// dp[l][r] = tree[id];
// vis[l][r] = true;
return;
}
void init (int n, vector <int>& ve) {
n=(n);
tree.resize(4*n);
// n = (1<<(__lg(n-1)));
// build(ve, 0, n-1, 0, 0);
build(ve, 0, n-1, 0, 0);
return;
}
int query (int ql, int qr, int l, int r, int id) {
if (qr < l || r < ql) return -1;
if (ql <= l && r <= qr) return tree[id];
int mid = (l+r)>>1;
int ansl = query(ql, qr, l, mid, 2*id+1);
int ansr = query(ql, qr, mid+1, r, 2*id+2);
if (min(ansl, ansr) == -1) return max(ansl, ansr);
return Secret(ansl, ansr);
}
// void solve (int niv) {
// if (niv == 0) return;
// vector <Segment> vn = nivs[niv];
// // for (Segment s : vn) {
// // cout<<s.l<<' ' << s.r<<' '<<s.id<<'\n';
// // }
// // cout<<endl;
// // for (int i = 1; i < vn.size(); i++) {
// // Segment ant = vn[i-1];
// // Segment act = vn[i];
// // // if (!(ant.r+1==act.l)) {
// // // cerr<<niv<<'\n'<<i<<'\n';
// // // cerr<<nivs[niv].size()<<'\n';
// // // }
// // assert(ant.r+1==act.l);
// // }
// // solve(niv-1);
// // return;
// for (int i = 1; i < vn.size(); i++) {
// Segment ant = vn[i-1];
// Segment act = vn[i];
// // assert(ant.r+1==act.l);
// for (int j = act.l; j <= min(act.r,n-1); j++) {
// assert(vis[act.l][j]);
// dp[ant.l][j] = Secret(dp[ant.l][ant.r], dp[act.l][j]);
// vis[ant.l][j] = true;
// }
// if(act.r>=n-1)break;
// }
// for (int i = 1; i < vn.size(); i++) {
// Segment ant = vn[i-1];
// Segment act = vn[i];
// for (int j = ant.l; j <= min(ant.r,n-1); j++) {
// assert(vis[j][ant.r]);
// dp[j][act.r] = Secret(dp[j][ant.r], dp[act.l][act.r]);
// vis[j][act.r] = true;
// }
// if(ant.r>=n-1)break;
// }
// // if (vis[ql][qr]) return dp[ql][qr];
// // vis[ql][qr] = true;
// // ll& ans = dp[ql][qr];
// solve(niv-1);
// return;
// }
};
int nn;
SegTree st;
void Init (int n, int a[]) {
nn=n;
vector <int> ve(n);
for (int i = 0; i < n; i++) {
ve[i] = a[i];
}
st.init(n, ve);
// for (ll i = 0; i < n; i++) {
// for (ll j = i; j < n; j++) {
// cerr<<i<<','<<j<<": "<<dp[i][j]<<'\n';
// }
// }
// st.solve(11);
return;
}
int Query (int l, int r) {
// cout << "counter: " << COUNT << '\n';
return st.query(l, r, 0, nn-1, 0);
}
// int main () {
// int n;
// cin >> n;
// int a[n];
// for (int i = 0; i < n; i++) cin >> a[i];
// Init(n, a);
// ll Q;
// cin >> Q;
// while(Q--){
// ll l,r;
// cin>>l>>r;
// cout<<Query(l,r)<<'\n';
// }
// return 0;
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
135 ms |
2652 KB |
Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 13 |
| 2 |
Partially correct |
137 ms |
2900 KB |
Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 14 |
| 3 |
Partially correct |
134 ms |
2648 KB |
Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 15 |
| 4 |
Partially correct |
395 ms |
4432 KB |
Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 15 |
| 5 |
Partially correct |
396 ms |
4352 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 15 |
| 6 |
Partially correct |
358 ms |
4260 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4 |
| 7 |
Partially correct |
446 ms |
4464 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16 |
| 8 |
Partially correct |
420 ms |
4260 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16 |
| 9 |
Partially correct |
412 ms |
4256 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16 |
| 10 |
Partially correct |
428 ms |
4464 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 16 |
