結果
問題 | No.905 Sorted? |
ユーザー |
![]() |
提出日時 | 2019-10-11 21:45:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,352 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 64,820 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 07:09:30 |
合計ジャッジ時間 | 2,445 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <iostream>#include <stdio.h>#include <vector>#define llint long long#define inf 1e9using namespace std;struct SegTree{int size;vector<int> seg;SegTree(){}SegTree(int size){this->size = size;seg.resize(1<<(size+1));}void init(){for(int i = 0; i < (1<<(size+1)); i++) seg[i] = inf;}void update(int i, int val){i += (1 << size);seg[i] = val;while(i > 1){i /= 2;seg[i] = min(seg[i*2], seg[i*2+1]);}}int query(int a, int b, int k, int l, int r){if(b < l || r < a) return inf;if(a <= l && r <= b) return seg[k];int lval = query(a, b, k*2, l, (l+r)/2);int rval = query(a, b, k*2+1, (l+r)/2+1, r);return min(lval, rval);}int query(int a, int b){if(a > b) return 0;return query(a, b, 1, 0, (1<<size)-1);}};llint n, Q;llint a[100005];SegTree segU(17), segD(17);int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 0; i < n; i++) cin >> a[i];segU.init(), segD.init();for(int i = 0; i < n-1; i++){if(a[i] < a[i+1]) segU.update(i, -1);else segU.update(i, 0);if(a[i] > a[i+1]) segD.update(i, -1);else segD.update(i, 0);}cin >> Q;llint l, r;for(int q = 0; q < Q; q++){cin >> l >> r;cout << segD.query(l, r-1) + 1 << " " << segU.query(l, r-1) + 1 << "\n";}flush(cout);return 0;}