oj.uz

Submission #1003857

# Submission time Handle Problem Language Result Execution time Memory
1003857 2024-06-20T19:08:18 Z MonoLith Global Warming (CEOI18_glo) C++17
10 / 100
 248 ms 33536 KB 
/*
   ॐ नमो भगवते वासुदेवाय नमः
   ॐ भूर्भुव: स्व: तत्सवितुर्वरेण्यं भर्गो देवस्य धीमहि धियो यो न: प्रचोदयात्।
*/
// all hail Infront of almighty lord krishna (jai shri krishna ji)
  #include<bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp>
  #include <ext/pb_ds/tree_policy.hpp>
  using namespace std;
  using namespace __gnu_pbds;
  #define int long long 
  const long long INF =1e18;
  template<class T>
  using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
  template<typename T> 
  using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
  const int N=1e5 + 10;
  const int mod = 998244353;  

  int  result(int a, int b)
  {
    return max(a,b); // desired changes are needed here 
  } 

  void update_tree(int node, int a, int b, int i, int j, int value,vector<int>&t) {
    
    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
      return;
      
      if(a >= i && b <= j) { // Segment is fully within range
          t[node] = max(0ll,value);
          return;
    }
  
    update_tree(node*2, a, (a+b)/2, i, j, value,t); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value,t); // Updating right child
  
    t[node] = result(t[node*2], t[node*2+1]); // Updating root with max value
  }
  
  int query_tree(int node, int a, int b, int i, int j,vector<int>&t) {
    
    if(a > b || a > j || b < i) return 0; // Out of range
  
    if(a >= i && b <= j) // Current segment is totally within range [i, j]
      return t[node];
  
    int q1 = query_tree(node*2, a, (a+b)/2, i, j,t); // Query left child
    int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j,t); // Query right child
  
    int res = result(q1, q2); // Return final result
    
    return res;
  }
  void Solve()
  {
    int n,x;
    cin>>n>>x;
    vector<int>a(n);
    set<int>s;
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
      s.insert(a[i]);
    }
    int curr=1;
    map<int,int>mp;
    for(auto it:s)
    {
      mp[it]=curr;
      curr++;
    }
    for(int i=0;i<n;i++)
    {
      a[i]=mp[a[i]];
    }
    vector<int>inc(n,0);
    vector<int>t(4*n+5,0);
    for(int i=0;i<n;i++)
    {
      auto it=query_tree(1,0,n-1,0,a[i]-1,t);
      inc[i]=it+1;
      update_tree(1,0,n-1,a[i],a[i],inc[i],t);
    }
    if(x==0)
    {
      cout<<*max_element(inc.begin(),inc.end())<<"\n";
      return ;
    }
    fill(t.begin(),t.end(),0);
    vector<int>dec(n,0);
    reverse(a.begin(),a.end());
    for(int i=0;i<n;i++)
    {
      auto it=query_tree(1,0,n-1,0,a[i]-1,t);
      dec[i]=it+1;
      update_tree(1,0,n-1,a[i],a[i],dec[i],t);
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
      ans=max(ans,inc[i]+dec[i]-1);
    }
    cout<<ans<<"\n";
}

  signed main()
  { 
    
      auto begin = std::chrono::high_resolution_clock::now();
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout<<fixed;
      int t = 1;
      // cin >> t;

      for(int i = 1; i <= t; i++) 
      {
          // cout << "Case #" << i << ": ";
          Solve();
 
      }
      auto end = std::chrono::high_resolution_clock::now();
      auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
      // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
      return 0;       
  }

Compilation message

glo.cpp: In function 'void update_tree(long long int, long long int, long long int, long long int, long long int, long long int, std::vector<long long int>&)':
glo.cpp:27:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |     if(a > b || a > j || b < i) // Current segment is not within range [i, j]
      |     ^~
glo.cpp:30:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |       if(a >= i && b <= j) { // Segment is fully within range
      |       ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 33468 KB Output is correct
2 Correct 248 ms 33536 KB Output is correct
3 Correct 227 ms 33536 KB Output is correct
4 Correct 243 ms 33444 KB Output is correct
5 Correct 113 ms 21812 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 9124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 17748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -