Submission #978112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978112	2024-05-08T20:11:18 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	813 ms	7896 KB

deda

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including
// tree_order_statistics_node_update #include
//<ext/pb_ds/detail/standard_policies.hpp>
#define S second
#define F first
#define vll vector<ll>
#define pll pair<ll, ll>
#define mll vector<vll>
#define sll set<ll>
#define vstring vector<string>
#define rep(x, g, y) for (ll x = g; x < y; x++)
#define rrep(x, g, y) for (ll x = g; x >= y; x--)
#define all(a) (a).begin(), (a).end()
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
// CRAM DEJA DE VER MIS ENVIOS MALDITO
// SUPER SET
// typedef tree<int, null_type, less<int>, rb_tree_tag,
// tree_order_statistics_node_update> ordered_set;

// SUPER MULTISET
// typedef tree<long long, null_type, less_equal<>, rb_tree_tag,
// tree_order_statistics_node_update> indexed_multiset;

// USOS
//  imprimer la cantidad de elementos escritamente menor a X
//   cout << aux.order_of_key(x)<<"\n";

// imprime el elemento k-esimo mas grande(comenzando desde 0)
// cout<<*X.find_by_order(K)<<endl;

// TIP: lower y upper invertidos en multiset.

// ll mod=1e9+7;
//  ll expo(ll a, ll b)
//  {
//      if(a==0) return b==0;
//      ll ans=1;
//      while (b)
//      {
//          if(b&1) ans=(ans*a)%mod;
//          b>>=1LL;
//          a=(a*a)%mod;
//      }
//      return ans;

// }

ll lcm(ll a, ll b) { return (a * b) / __gcd(a, b); }

void yes() { cout << "YES\n"; }

void no() { cout << "NO\n"; }

template <class T> void print_v(vector<T> &v) {
  cout << "{";
  for (auto x : v)
    cout << x << ",";
  cout << "\b}\n";
}
void update(vll &st, ll l, ll r, ll nd, ll pos, ll valor) {
  ll mid = (l + r) / 2;
  if (l == r) {
    st[nd] = valor;
    return;
  }
  if (pos <= mid)
    update(st, l, mid, nd * 2, pos, valor);
  else
    update(st, mid + 1, r, nd * 2 + 1, pos, valor);
  st[nd] = min(st[nd * 2], st[nd * 2 + 1]);
}

ll query(vll &st, ll l, ll r, ll nd, ll lq, ll rq) {
    if(lq<=l && r<=rq) return st[nd];

    if(r<lq || l>rq) return 1e12;

    ll mid=(l+r)/2;
    return min(query(st, l, mid, nd*2,lq,rq), query(st,mid+1,r,nd*2+1,lq,rq));

}
void solve() {
  ll n, q;
  cin >> n >> q;
  vll st(4*n,1e12);
  while (q--) {
    char x;
    cin >> x;
    ll a, b;
    cin >> a >> b;
    if (x == 'M')
    {
        update(st, 0, n - 1, 1, --b, a);
    }

    else
    {
        ll inicio=--b;
        ll fin=n-1;
        ll ans=-2;
        while(inicio<=fin)
        {
            ll mid=(inicio+fin)/2;
            if(query(st, 0, n-1, 1, b,mid)<=a)
            {
                ans=mid;
                fin=mid-1;
            }
            else inicio=mid+1;

        }
        cout << ans+1<<"\n";

    }

    //print_v(st);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  // ll t; cin >> t;
  // while(t--)
  solve();

  return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	456 KB	Output is correct
3	Correct	6 ms	508 KB	Output is correct
4	Correct	813 ms	7896 KB	Output is correct
5	Correct	483 ms	4300 KB	Output is correct
6	Correct	556 ms	5976 KB	Output is correct
7	Correct	639 ms	7476 KB	Output is correct