結果
問題 | No.905 Sorted? |
ユーザー |
![]() |
提出日時 | 2019-10-11 21:40:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 2,937 bytes |
コンパイル時間 | 1,905 ms |
コンパイル使用メモリ | 178,432 KB |
実行使用メモリ | 9,712 KB |
最終ジャッジ日時 | 2024-11-25 07:03:02 |
合計ジャッジ時間 | 6,043 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)#define itn int#define all(x) (x).begin(),(x).end()#define F first#define S secondconst long long INF = 1LL << 60;const int MOD = 1000000007;template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }struct SegTree{int n;vector <int> node;SegTree(vector <int> v){int sz = v.size();n = 1;while(n<sz) n*=2;node.resize(2*n-1, INF);for(int i=0; i<sz; i++) node[i+n-1] = v[i]; //一番下側for(int i=n-2;i>=0;i--) node[i] = min(node[2*i+1], node[2*i+2]);}void update(int number, int val){number += n-1;node[number]= val;while(number>0){number=(number-1)/2;node[number] = min(node[number*2+1], node[number*2+2]);}}int getmin(int a, int b, int k=0, int l = 0, int r = -1){if(r<0) r=n;if(r<=a||l>=b) return INF;if(a <= l&& r<=b) return node[k];int vl = getmin(a, b, 2*k+1, l, (l+r)/2);int vr = getmin(a, b, 2*k+2, (l+r)/2, r);return min(vl, vr);}};//参考:http://tsutaj.hatenablog.com/entry/2017/03/29/204841struct maxSegTree{int n;vector <int> node;maxSegTree(vector <int> v){int sz = v.size();n = 1;while(n<sz) n*=2;node.resize(2*n-1, -114514);for(int i=0; i<sz; i++) node[i+n-1] = v[i]; //一番下側for(int i=n-2;i>=0;i--) node[i] = max(node[2*i+1], node[2*i+2]);}void update(int number, int val){number += n-1;node[number]= val;while(number>0){number=(number-1)/2;node[number] = max(node[number*2+1], node[number*2+2]);}}int getmax(int a, int b, int k=0, int l = 0, int r = -1){if(r<0) r=n;if(r<=a||l>=b) return -114514;if(a <= l&& r<=b) return node[k];int vl = getmax(a, b, 2*k+1, l, (l+r)/2);int vr = getmax(a, b, 2*k+2, (l+r)/2, r);return max(vl, vr);}};//参考:http://tsutaj.hatenablog.com/entry/2017/03/29/204841signed main(void){int n; cin>>n;vector <int> a(n);rep(i,n) cin>>a[i];vector <int> c;rep(i,n-1){if(a[i] == a[i+1]) c.push_back(0);else if(a[i] < a[i+1]) c.push_back(1);else c.push_back(-1);}SegTree miseg(c);maxSegTree maseg(c);int q; cin>>q;rep(i,q){int a,b; cin>>a>>b;int ma = maseg.getmax(a,b);int mi = miseg.getmin(a,b);if(mi != -1) cout<<1<<' ';else cout<<0<<' ';if(ma == 1) cout<<0<<endl;else cout<<1<<endl;}}