답안 #82220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82220	2018-10-29T14:10:38 Z	wjoao	Deda (COCI17_deda)	C++11	140 / 140	189 ms	19076 KB

deda

#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

#	결과	실행 시간	메모리	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