#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
int n;
int Secret(int X, int Y);
struct SGT{
vector<int> t;
vector<vector<int>> p;
vector<vector<int>> s;
int n;
int *a;
SGT()
{
}
void
init(int _n, int *_a)
{
a = _a;
n = _n;
t.resize(4*n);
p.resize(4*n);
s.resize(4*n);
build(1,0,n-1);
}
int
queryval(int i, int l, int r, int tl, int tr)
{
/* printf("QV %d: l(%d) r(%d) mid(%d) tl(%d) tr(%d)\n", */
/* i, l, r, (l+r)>>1,tl,tr); */
if (l > tr || r < tl) return 0;
if (tl < l && tr > r) return 0;
if (tl == l && tr == r) return t[i];
int mid = (l+r)>>1;
/* if (l < tl && r > tr) { */
/* cout << "Bazinga" << endl; */
/* return queryval(i<<1, l, mid, tl, tr) + queryval(i<<1|1, mid+1, r, tl, tr); */
/* } */
if (l == r)
return t[i];
if (tl == l) {
if (tr <= mid) {
return queryval(i<<1,l,mid,tl,tr);
} else {
return p[i][tr - mid-1];
}
}
if (tr == r) {
if (tl > mid) {
return queryval(i<<1|1,mid+1,r,tl,tr);
} else {
return s[i][mid-tl];
}
}
if (tl == mid+1)
return queryval(i<<1|1, mid+1, r, tl, tr);
if (tr == mid)
return queryval(i<<1, l, mid, tl, tr);
assert(0);
return queryval(i<<1, l, mid, tl, tr) + queryval(i<<1|1, mid+1, r, tl, tr);
}
void
build(int i, int l, int r)
{
/* printf("Building %d: l(%d) r(%d) mid(%d)\n", i, l, r, (l+r)>>1); */
if (l == r) {
p[i].pb(a[l]);
s[i].pb(a[l]);
t[i] = a[l];
/* cout << i << ": " << t[i] << endl; */
return;
}
int mid = (l+r)>>1;
build(i<<1, l, mid);
build(i<<1|1, mid+1, r);
for (int j = mid+1; j <= r; ++j) {
/* printf("\t0: %d\n", queryval(i<<1|1,mid+1,r,mid+1,j)); */
p[i].pb(Secret(t[i<<1],queryval(i<<1|1,mid+1,r,mid+1,j)));
}
for (int j = mid; j > l; --j) {
/* printf("\t1: %d\n", queryval(i<<1,l,mid,j,mid)); */
s[i].pb(Secret(queryval(i<<1,l,mid,j,mid),t[i<<1|1]));
}
t[i] = p[i][sz(p[i])-1];
/* printf("Building %d: l(%d) r(%d) mid(%d) t(%d)\n", i, l, r, (l+r)>>1,t[i]); */
/* for (int j = 0; j < sz(p[i]); ++j) { */
/* printf("\t%d %d\n",j,p[i][j]); */
/* } */
/* for (int j = 0; j < sz(s[i]); ++j) { */
/* printf("\t%d %d\n",j,s[i][j]); */
/* } */
return;
}
int
query(int i, int l, int r, int tl, int tr)
{
/* printf("Quering %d: l(%d) r(%d) mid(%d) tl(%d) tr(%d)\n", */
/* i, l, r, (l+r)>>1,tl,tr); */
if (l == tl && r == tr) {
return t[i];
}
if (l > tr || r < tl) return 0;
if (tr > r || l > tl) assert(0);
if (l == tl)
return queryval(i,l,r,tl,tr);
if (r == tr)
return queryval(i,l,r,tl,tr);
int mid = (l+r)>>1;
if (tl > mid) return query(i<<1|1,mid+1,r,tl,tr);
if (tr < mid+1) return query(i<<1,l,mid,tl,tr);
return Secret(queryval(i<<1,l,mid,tl,mid),
queryval(i<<1|1,mid+1,r,mid+1,tr));
}
int query(int l, int r) { return query(1,0,n-1,l,r); }
};
SGT tr;
void
Init(int _n, int a[])
{
n = _n;
tr.init(n,a);
return;
}
int
Query(int l, int r)
{
return tr.query(l,r);
}
#ifdef ONPC
int
Secret(int X, int Y)
{
return X + Y;
}
void
solve()
{
int _n;
int q;
cin >> _n >> q;
int a[_n];
for (int i = 0; i < _n; ++i)
cin >> a[i];
Init(_n,a);
int x, y;
while (q--) {
cin >> x >> y;
--x,--y;
cout << Query(x, y) << endl;
}
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
2512 KB |
Output is correct - number of calls to Secret by Init = 4088, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
131 ms |
2484 KB |
Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
119 ms |
2508 KB |
Output is correct - number of calls to Secret by Init = 4107, maximum number of calls to Secret by Query = 1 |
| 4 |
Partially correct |
445 ms |
4608 KB |
Output isn't correct - number of calls to Secret by Init = 8967, maximum number of calls to Secret by Query = 1 |
| 5 |
Partially correct |
438 ms |
4624 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
| 6 |
Partially correct |
433 ms |
4556 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
| 7 |
Partially correct |
455 ms |
4548 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
| 8 |
Partially correct |
428 ms |
4528 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
| 9 |
Partially correct |
439 ms |
4576 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
| 10 |
Partially correct |
454 ms |
4552 KB |
Output isn't correct - number of calls to Secret by Init = 8977, maximum number of calls to Secret by Query = 1 |
