結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー edamame882
提出日時 2019-09-25 16:05:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,084 bytes
コンパイル時間 1,737 ms
コンパイル使用メモリ 175,632 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 07:38:41
合計ジャッジ時間 3,906 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

struct segTree{
  int n;
  vector<PII> node;

  void init(int x){
    n = 1;
    while(n < x) n *= 2;
    node.resize(n*2-1,PII(INT_MAX,INT_MAX));
  }

  void update(int i, int x){
    i += (n-1);
    node[i] = PII(x,i-(n-1));
    while(i > 0){
      i = (i-1)/2;
      node[i] = min(node[i*2 +1],node[i*2+2]);
    }
  }

  PII getMin(int x, int y, int k=0, int l=0, int r=-1){
    if(r < 0) r = n;
    if(r<=x || l>=y) return PII(INT_MAX,INT_MAX);
    if(x<=l && r<=y) return node[k];

    PII vl = getMin(x, y, 2*k+1, l, (l+r)/2);
    PII vr = getMin(x, y, 2*k+2, (l+r)/2, r);
    return min(vl,vr);
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,q;
  cin >> n >> q;
  segTree t;
  t.init(n);

  rep(i,n){
    int a;
    cin >> a;
    t.update(i,a);
  }

  rep(i,q){
    int cmd;
    cin >> cmd;
    if(cmd == 1){
      int x,y;
      cin >> x >> y;
      x--,y--;
      // cerr << "(x,y) = "  << x << " , " << y << endl;
      int r = t.node.at(x+(n)).first;
      int l = t.node.at(y+(n)).first;
      // cerr << "(l,r) = "  << r << " , " << l << endl;
      t.update(x,l);
      t.update(y,r);
    }else{
      int x,y;
      cin >> x >> y;
      x--,y--;
      cout << t.getMin(x,y+1).second + 1 << endl;
    }
  }
  return 0;
}
0