Submission #411193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411193	2021-05-24T14:53:27 Z	singh	Deda (COCI17_deda)	C++14	140 / 140	594 ms	7832 KB

deda

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5;
pair<int,int>  tv[4*maxn]; 
int arr[maxn];
int dist[maxn];
 pair<int,int> combine(pair<int,int> a, pair<int,int> b)
{
    if(a.first>b.first)
     return b;
     else if(b.first>a.first)
          return a;

}

 void build(int v,int tl,int tr)
 {
   if(tl==tr)
  tv[v]={dist[arr[tl]],arr[tl]};

    else
    {
      int mid=(tl+tr)/2;
       build(v*2,tl,mid);
      build(v*2+1,mid+1,tr);
      tv[v]=combine(tv[v*2],tv[v*2+1]);
    }
   }

pair<int,int> get_first(int v, int lv, int rv, int l, int r, int x) {
    if(lv > r || rv < l) return {-1,-1};
    if(l <= lv && rv <= r) {
        if(tv[v].first> x) return {-1,-1};
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(tv[2*v].first <= x) {
                v = 2*v;
                rv = mid;
            }else {
                v = 2*v+1;
                lv = mid+1;
            }
        }
        return {arr[lv],tv[lv].first};
    }

    int mid = lv + (rv-lv)/2;
    pair<int,int> rs = get_first(2*v, lv, mid, l, r, x);
    if(rs.first != -1) return rs;
    return get_first(2*v+1, mid+1, rv, l ,r, x);
}

void update(int v, int tl, int tr, int pos,int new_val) {
    if (tl == tr) {
        tv[v]={new_val,arr[tl]};
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        tv[v] = combine(tv[v*2], tv[v*2+1]);
    }
}
int main()
{

  int n,q;
  cin>>n>>q;
   for(int i=1;i<=n;i++)
   {
     arr[i]=i;
     dist[i]=INT_MAX;
     
   }  
   build(1,1,n);
   while(q--)
   {
     int b,c;
     char a;
     cin>>a>>b>>c;
     if(a=='M')   
      update(1,1,n,c,b);   
     else{
      pair<int,int>  r=get_first(1,1,n,c,n,b);
      cout<<r.first<<endl;
       }
   }
}

Compilation message

deda.cpp: In function 'std::pair<int, int> combine(std::pair<int, int>, std::pair<int, int>)':
deda.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	2 ms	296 KB	Output is correct
3	Correct	11 ms	384 KB	Output is correct
4	Correct	594 ms	7832 KB	Output is correct
5	Correct	464 ms	4636 KB	Output is correct
6	Correct	543 ms	7116 KB	Output is correct
7	Correct	542 ms	7724 KB	Output is correct