oj.uz

Submission #82220

# Submission time Handle Problem Language Result Execution time Memory
82220 2018-10-29T14:10:38 Z wjoao Deda (COCI17_deda) C++11
140 / 140
 189 ms 19076 KB 
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define zero inf
#define maxn 200010

using namespace std;

struct SegmentTree{
    int st[4*maxn];
	// Array inicial.
    int vet[maxn];
    // tamanho
    int tam;

    int join(int a, int b){
		  return min(a ,b);
    }

    void build(int n){
      tam = n;
      memset(vet, inf, sizeof vet);
      memset(st, inf, sizeof st);
    }

    int query( int i, int y ){
      return query( 1, 0, tam-1, i, y );
    }
    
    int query( int p, int L, int R, int i, int y ){
      //cout << "Query: " << p << " st[p]: " << st[p] << " L: " << L << " R: " << R << endl;
      if( i > R ) return zero; // Fora do range da query
      if( st[p] > y ) return zero;
      if( L == R ) return L;

      int p1 = query(p*2, L, (L+R)/2, i, y );

      if( p1 == zero ) return query(p*2+1, (L+R)/2 + 1, R, i, y);
      return p1;
    }

    void update(int i, int val){
		  return update( 1, 0, tam-1, i, val );
    }

    void update(int p, int L, int R, int i, int val){
      if( i > R || i < L ) return; // Fora do range do update
      if( L == i && R == i ){ // Totalmente dentro do range do update
        st[p] = val;
        return;
      }

      update(p*2, L, (L+R)/2, i, val);
      update(p*2+1, (L+R)/2 + 1, R, i, val);
      st[p] = join( st[p*2], st[p*2+1] );
    }
} segtree;

int n, q, a, b;
char op;
int main(){
  scanf(" %d %d", &n, &q);
  segtree.build(n);
  for(int i = 0; i < q; i++){
    scanf(" %c %d %d", &op, &a, &b);
    if(op == 'M'){
      //cout << "Inserindo no: " << b << " o valor: " << a << endl;
      segtree.update(b-1, a);
    }else{
      //cout <<" Consultando a partir de b: " << b << " Todos os valores menores que : " << a << endl;
      int r = segtree.query(b-1, a);
      if( r == inf) printf("-1\n");
      else printf("%d\n", r+1);
    }
  }


  return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~
deda.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %c %d %d", &op, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4380 KB Output is correct
3 Correct 8 ms 4380 KB Output is correct
4 Correct 129 ms 8872 KB Output is correct
5 Correct 189 ms 11896 KB Output is correct
6 Correct 148 ms 15484 KB Output is correct
7 Correct 162 ms 19076 KB Output is correct