oj.uz

Submission #928085

# Submission time Handle Problem Language Result Execution time Memory
928085 2024-02-15T20:25:59 Z xad Deda (COCI17_deda) C++17
140 / 140
 88 ms 8788 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
int fx[]={1,-1,0,0}, fy[]={0,0,1,-1};
int sgt[1000001]={}, n;
void upd(int s, int e, int l, int df,int i=0)
{
if(l<s||l>e)return ;
if(s!=e)
{int mid=(s+e)/2; upd(s,mid,l,df,i*2+1); upd(mid+1,e,l,df,i*2+2);}
if (s==e&&s==l)sgt[i]=df;
else
    sgt[i] = min(sgt[i*2+1],sgt[i*2+2]);
}
int mn(int s,int e, int l, int r, int v,int i=0)
{
if(r<s||l>e)
     return 1000000005;
if(s>=l&&e<=r&&sgt[i]>v)
     return 1000000005;
if(s==e&&s>=l&&e<=r)
     return s;
int mid=(s+e)/2;
int a=mn(s,mid,l,r,v,i*2+1);
if(a<=n) return a;
a=mn(mid+1,e,l,r,v,i*2+2);
return a;
}
int main() {
    /*freopen("measurement.in","r",stdin);
    freopen("measurement.out","w", stdout);*/

    x_x
    int q; cin>>n>>q; int ar[n];
    for (int i=0; i<1000000; i++) sgt[i]=1000000005;
   // for (auto&i:ar) i=1000000005;
    while (q--) {
        char c; int a,b; cin>>c>>a>>b;
        if (c=='M') {
            upd(1,n,b,a);
        }
        else {
            int x=mn(1,n,b,n,a); cout<<(x>n?-1:x);
     if(q>0)cout<<nn;
        }
    }

    //upd(1,4, 3, 2); cout<<mn(1,4,1,3,5);
   return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:49:27: warning: unused variable 'ar' [-Wunused-variable]
   49 |     int q; cin>>n>>q; int ar[n];
      |                           ^~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 88 ms 8788 KB Output is correct
5 Correct 80 ms 8168 KB Output is correct
6 Correct 84 ms 8404 KB Output is correct
7 Correct 87 ms 8768 KB Output is correct