Submission #411074

# Submission time Handle Problem Language Result Execution time Memory
411074 2021-05-24T09:25:16 Z singh Deda (COCI17_deda) C++14
20 / 140
2 ms 460 KB
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
pair<int,int>  tv[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:13:1: warning: control reaches end of non-void function [-Wreturn-type]
   13 | }
      | ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 2 ms 204 KB Output isn't correct
3 Runtime error 2 ms 332 KB Execution killed with signal 11
4 Runtime error 1 ms 448 KB Execution killed with signal 11
5 Runtime error 2 ms 332 KB Execution killed with signal 11
6 Runtime error 2 ms 332 KB Execution killed with signal 11
7 Runtime error 1 ms 460 KB Execution killed with signal 11