oj.uz

Submission #111631

# Submission time Handle Problem Language Result Execution time Memory
111631 2019-05-15T22:02:53 Z aleksami Deda (COCI17_deda) C++14
120 / 140
 1000 ms 7080 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 11 ms 496 KB Output is correct
4 Execution timed out 1070 ms 6824 KB Time limit exceeded
5 Correct 709 ms 5652 KB Output is correct
6 Correct 899 ms 6740 KB Output is correct
7 Correct 977 ms 7080 KB Output is correct