This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 2e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long n, a[MAXN];
void read_array()
{
cin >> n;
for (long long i = 1; i <= n; ++ i)
{
cin >> a[i];
}
}
struct node
{
long long mineven, maxeven, minodd, maxodd;
node(){};
node(long long _mineven, long long _maxeven, long long _minodd, long long _maxodd)
{
mineven = _mineven;
maxeven = _maxeven;
minodd = _minodd;
maxodd = _maxodd;
}
};
node t[4 * MAXN];
void make_tree(long long i, long long l, long long r)
{
if(l == r)
{
if(a[l] & 1)
{
t[i].maxodd = a[l];
t[i].minodd = a[l];
t[i].maxeven = -1;
t[i].mineven = 1e17;
}
else
{
t[i].maxeven = a[l];
t[i].mineven = a[l];
t[i].maxodd = -1;
t[i].minodd = 1e17;
}
return;
}
long long mid = (l + r)/2;
make_tree(2*i, l, mid);
make_tree(2*i+1, mid+1, r);
t[i].maxodd = max(t[2*i].maxodd, t[2*i+1].maxodd);
t[i].minodd = min(t[2*i].minodd, t[2*i+1].minodd);
t[i].maxeven = max(t[2*i].maxeven, t[2*i+1].maxeven);
t[i].mineven = min(t[2*i].mineven, t[2*i+1].mineven);
}
long long ql, qr;
pair < long long/**minimum even*/, long long/**maxodd*/> query(long long i, long long l, long long r)
{
// cout << i << " " << l << " " << r << endl;
if(qr < l || ql > r)return make_pair(1e17, -1);
if(ql <= l && r <= qr)
{
return make_pair(t[i].mineven, t[i].maxodd);
}
long long mid = (l + r)/2;
pair < long long , long long > first_half = query(2*i, l, mid);
pair < long long, long long > second_half = query(2*i+1, mid+1, r);
pair < long long, long long > ans = make_pair(min(first_half.first, second_half.first), max(first_half.second, second_half.second));
return ans;
}
int main()
{
speed();
read_array();
make_tree(1, 1, n);
long long q;
cin >> q;
long long type;
while(q --)
{
cin >> type;
if(type == 1)
{
cin >> ql >> qr;
pair < long long, long long > qq = query(1, 1, n);
if(qq.first == 1e17)cout << -1 << " ";
else cout << qq.first << " ";
if(qq.second == -1)cout << -1 << endl;
else cout << qq.second << endl;
//cout << .first << " " << query(1, 1, n).second << endl;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |