oj.uz

Submission #111632

# Submission time Handle Problem Language Result Execution time Memory
111632 2019-05-15T22:21:02 Z aleksami Deda (COCI17_deda) C++14
140 / 140
 106 ms 3584 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 82 ms 3584 KB Output is correct
5 Correct 89 ms 2172 KB Output is correct
6 Correct 97 ms 3320 KB Output is correct
7 Correct 106 ms 3344 KB Output is correct