Submission #111631

#	Time	Username	Problem	Language	Result	Execution time	Memory
111631		aleksami	Deda (COCI17_deda)	C++14	120 / 140	1070 ms	7080 KiB

deda

#include <bits/stdc++.h>

using namespace std;
#define MAXN 200005
int tree[4*MAXN];
const int INF = 1e9;

void update(int node,int left,int right,int idx,int val)
{
  if(left == right)
  {
    tree[node]=val;
    return ;
  }
  int mid=left+right>>1;
  if(idx <= mid)update(node*2,left,mid,idx,val);
  else update(node*2+1,mid+1,right,idx,val);
  tree[node]=min(tree[node*2],tree[node*2+1]);
}
int query(int node,int left,int right,int l,int r)
{
  if(left > right || left > r || l > right)return INF;
  if(left >= l && right <= r)return tree[node];
  int mid=left+right>>1;
  return min(query(node*2,left,mid,l,r),query(node*2+1,mid+1,right,l,r));
}
void build(int node,int left,int right)
{
  if(left == right)
  {
    tree[node]=INF;
    return ;
  }
  if(left > right)return ;
  int mid=left+right>>1;
  build(node*2,left,mid);
  build(node*2+1,mid+1,right);
  tree[node]=min(tree[node*2],tree[node*2+1]);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,q;
  cin >> n >> q;
  build(1,1,n);
  while(q--)
  {
    char c;
    int x,y;
    cin >> c >> x >> y;
    if(c=='D')
    {
      int lo=y,hi=n,mid=lo+hi>>1,r=-1;
      while(lo <= hi)
      {
        if(query(1,1,n,y,mid)<=x)r=mid,hi=mid-1;
        else lo=mid+1;
        mid=lo+hi>>1;
      }
      cout << r << "\n";
    }
    else 
    {
      update(1,1,n,y,x);
    }
  }
  return 0;
}

Compilation message (stderr)

deda.cpp: In function 'void update(int, int, int, int, int)':
deda.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=left+right>>1;
           ~~~~^~~~~~
deda.cpp: In function 'int query(int, int, int, int, int)':
deda.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=left+right>>1;
           ~~~~^~~~~~
deda.cpp: In function 'void build(int, int, int)':
deda.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=left+right>>1;
           ~~~~^~~~~~
deda.cpp: In function 'int main()':
deda.cpp:56:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int lo=y,hi=n,mid=lo+hi>>1,r=-1;
                         ~~^~~
deda.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         mid=lo+hi>>1;
             ~~^~~

• Subtask 1: 120 / 140