fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for (ll i = (a); i < (b); i++)
  7. #define ROF(i,a,b) for (ll i = (a); i >= (b); i--)
  8. #define csort(a) sort(a.begin(), a.end())
  9.  
  10. class Segtree {
  11.     vector<ll> tree;
  12.     vector<ll> lazy;
  13.     ll n;
  14.     vector<ll> l1;
  15. public:
  16.     Segtree(ll _n) {
  17.         n = _n;
  18.         tree.assign(4 * n + 1, -1);
  19.         lazy.assign(4 * n + 1, 0);
  20.     }
  21.  
  22.     ll query(ll l, ll r, ll tl, ll tr, ll node) {
  23.         // push(l, r, node);
  24.         if (l > tr || r < tl) return -1;
  25.         if (l >= tl && r <= tr) return tree[node];
  26.         ll mid = (l + r) / 2;
  27.         return max(query(l, mid, tl, tr, node * 2), query(mid + 1, r, tl, tr, node * 2 + 1));
  28.     }
  29.  
  30.     void update(ll l, ll r, ll t, ll val, ll node) {
  31.         // push(l, r, node);
  32.         if (r < t || l > t) return;
  33.         if (l == t && r == t) {
  34.             tree[node] = val;
  35.             return;
  36.         }
  37.         ll mid = (l + r) / 2;
  38.         update(l, mid, t, val, node * 2);
  39.         update(mid + 1, r, t, val, node * 2 + 1);
  40.         tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
  41.     }
  42.     void update(ll t, ll val){
  43.         update(0, n-1, t, val, 1);
  44.     }
  45.     ll query(ll l, ll r){
  46.         return query(0, n-1, l, r, 1);
  47.     }
  48. };
  49.  
  50. void solve() {
  51.     ll n,q;
  52.     cin >> n >> q;
  53.     vector <ll> l1(n);
  54.     for (int i = 0; i < n; i++) cin >> l1[i];
  55.     vector <Segtree> f;
  56.     for (int i = 0; i < 3; i++){
  57.         f.emplace_back(n+2);
  58.     }
  59.     Segtree v = Segtree(n+ 2);
  60.     for (int i = 0; i < n; i++){
  61.         for (int x = 0; x < 3; x++){
  62.             if (x ==0){
  63.                 f[0].update(l1[i], i); continue;
  64.             }
  65.             ll cur = f[x-1].query(l1[i] + 1, n + 1);
  66.             f[x].update(l1[i], cur);
  67.             if (x == 2){
  68.                 v.update(i, cur);
  69.             }
  70.         }
  71.     }
  72.     for (int i = 0; i < q; i++){
  73.         ll l, r;
  74.         cin >> l >> r;
  75.         if (v.query(l-1,r-1) >= l-1){
  76.             cout << "NO" << "\n";
  77.         }
  78.         else{
  79.             cout << "YES" << "\n";
  80.         }
  81.     }
  82. }
  83.  
  84. int main() {
  85.     ios::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.  
  88.     int t; cin >> t; while(t--)solve();
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qJyNS8
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!