Submission #645319

#TimeUsernameProblemLanguageResultExecution timeMemory
645319notmeSimple (info1cup19_simple)C++14
0 / 100
140 ms13400 KiB
#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; cout << query(1, 1, n).first << " " << query(1, 1, n).second << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...