Submission #111632

#	Time	Username	Problem	Language	Result	Execution time	Memory
111632		aleksami	Deda (COCI17_deda)	C++14	140 / 140	106 ms	3584 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 idx,int req)
{
  if(left == right && tree[node] <= req && left >= idx)return left;
  else if(left == right)return -1;
  int mid=left+right>>1;
  int ret = -1;
  if(tree[node*2]<=req && mid >= idx)ret=query(node*2,left,mid,idx,req);
  if(ret!=-1)return ret;
  if(tree[node*2+1]<=req)ret=query(node*2+1,mid+1,right,idx,req);
  return ret;
}
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')
    {
      cout << query(1,1,n,y,x) << "\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:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=left+right>>1;
           ~~~~^~~~~~

• Subtask 1: 140 / 140