/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 2.527 MiB
#2 Accepted 2ms 2.324 MiB
#3 Accepted 231ms 16.867 MiB
#4 Accepted 214ms 16.391 MiB
#5 Accepted 200ms 17.359 MiB
#6 Accepted 198ms 17.961 MiB
#7 Accepted 2ms 2.527 MiB
#8 Accepted 3ms 2.551 MiB
#9 Accepted 239ms 17.762 MiB
#10 Accepted 255ms 17.859 MiB

Code


#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'

const int N = 5e5 + 9;

struct node
{
  int prefix, suffix, sorted;
};

node t[4 * N];
int lazy[4 * N];
int a[N];

node merge(node l, node r)
{ // what question need ??
  if (l.prefix == -1)
    return r;
  if (r.prefix == -1)
    return l;
  node ans;
  ans.prefix = l.prefix;
  ans.suffix = r.suffix;
  if (l.suffix <= r.prefix)
  {
    ans.sorted = max(l.sorted, r.sorted);
  }
  else
  {

    ans.sorted = 1;
  }
  return ans;
}

void build(int n, int b, int e)
{

  if (b == e)
  {
    t[n].prefix = a[b];
    t[n].suffix = a[b];
    t[n].sorted = 0;
    return;
  }
  int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
  build(l, b, mid);
  build(r, mid + 1, e);
  t[n] = merge(t[l], t[r]);
}

void upd(int n, int b, int e, int i, int j, int v)
{

  if (e < i or j < b)
    return;
  if (b >= i and e <= j)
  {
    t[n].suffix = t[n].prefix = v;
    t[n].sorted = 0;
    return;
  }
  int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
  upd(l, b, mid, i, j, v);
  upd(r, mid + 1, e, i, j, v);
  t[n] = merge(t[l], t[r]);
}

node query(int n, int b, int e, int i, int j)
{
   node x ;
   x.prefix = -1;
  if (e < i or j < b)
    return x; // resutl
  if (b >= i and e <= j)
  {
    return t[n]; // result
  }
  int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
  return merge(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // result
}

void solve()
{
  int n, q;
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  build(1, 1, n);
  cin >> q;
  while (q--)
  {
    int type;
    cin >> type;
    if (type == 1)
    {
      int i, x;
      cin >> i >> x;
      upd(1, 1, n, i, i, x);
    }
    else
    {
      int l, r;
      cin >> l >> r;

      node ans = query(1, 1, n, l, r);
      if (ans.sorted >= 1)
      {
        cout << "NO\n";
      }
      else
        cout << "YES\n";
      // cout << ans.value << endl;
    }
  }
}

int32_t main()
{

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  for (int j = 1; j <= t; j++)
  {
    // cout << "Case " << j << ":\n";
    solve();
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 16:07:10
Judged At
2024-10-03 13:28:34
Judged By
Score
100
Total Time
255ms
Peak Memory
17.961 MiB