oj.uz

답안 #605339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605339 2022-07-25T15:49:14 Z inksamurai Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 1481 ms 163444 KB 
//https://hsin.hr/coci/archive/2015_2016/results.php?contest=3
//Lovro Pužar
#define NDEBUG
#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define repeat(n) for (int repc = (n); repc > 0; --repc)
template<typename T, typename U> inline bool makemin(T &res, const U &x) {
  if (x < res) {
    res = x;
    return true;
  }
  return false;
}
template<typename T, typename U> inline bool makemax(T &res, const U &x) {
  if (x > res) {
    res = x;
    return true;
  }
  return false;
}

const int MAXN = 100005;
const int MAXK = 50;

int K;

struct TournamentTree {
  TournamentTree(int n) : n(n), nodes_(4*n) { }

  void update(int pos, int upd, bool defer) {
    update(0, 1, n, pos, upd, defer);
  }

  void build() {
    build(0, 1, n);
  }

  int query() {
    return nodes_[0].ans_;
  }

private:
  struct Node {
    Node() {
      for (int k=1; k<=K; ++k) {
        minp[k] = INT_MAX;
        maxp[k] = INT_MIN;
      }
    }
    void set_single(int pos, int val) {
      if (val_ != -1) {
        minp[val_] = INT_MAX;
        maxp[val_] = INT_MIN;
      }
      val_ = val;
      minp[val] = maxp[val] = pos;
      ans_ = K == 1 ? 1 : INT_MAX;
    }
    int val_ = -1;
    int minp[MAXK+1], maxp[MAXK+1];
    int ans_;
  };

  void update(int node, int a, int b, int pos, int val, bool defer) {
    if (a == pos && b == pos) {
      nodes_[node].set_single(pos, val);
      return;
    }

    int mid = (a+b) / 2;
    if (pos <= mid) {
      update(2*node+1, a, mid, pos, val, defer);
    } else {
      update(2*node+2, mid+1, b, pos, val, defer);
    }
    if (!defer) {
      merge(nodes_[node], nodes_[2*node+1], nodes_[2*node+2]);
      // fprintf(stderr, "merge(a=%d, b=%d) => %d\n", a, b, nodes_[node].ans_);
    }
  }

  void build(int node, int a, int b) {
    if (a < b) {
      int mid = (a+b) / 2;
      build(2*node+1, a, mid);
      build(2*node+2, mid+1, b);
      // fprintf(stderr, "merge(a=%d, b=%d) ...\n", a, b);
      merge(nodes_[node], nodes_[2*node+1], nodes_[2*node+2]);
      // fprintf(stderr, "build(a=%d, b=%d) => %d\n", a, b, nodes_[node].ans_);
    }
  }

  void merge(Node& out, const Node& in1, const Node& in2) {
    out.ans_ = min(in1.ans_, in2.ans_);
    for (int k=1; k<=K; ++k) {
      out.minp[k] = min(in1.minp[k], in2.minp[k]);
      out.maxp[k] = max(in1.maxp[k], in2.maxp[k]);
    }

    static vector<pair<int, int> > vp;
    vp.clear();
    int right = -1;
    for (int k=1; k<=K; ++k) {
      if (in1.maxp[k] != INT_MIN) {
        vp.push_back(make_pair(in1.maxp[k], k));
      } else if (in2.minp[k] != INT_MAX) {
        makemax(right, in2.minp[k]);
      } else {
        return;
      }
    }
    sort(vp.begin(), vp.end());
    for (int i=0; i<(int)vp.size(); ++i) {
      int maxp, k;
      tie(maxp, k) = vp[i];
      // fprintf(stderr, "  k = %d, right = %d, maxp = %d\n", k, right, maxp);
      if (right != -1) {
        makemin(out.ans_, right - maxp + 1);
      }
      if (in2.minp[k] == INT_MAX) {
        break;
      }
      makemax(right, in2.minp[k]);
    }
  }

  int n;
  vector<Node> nodes_;
};

int main() {
  ios_base::sync_with_stdio(0); // caret here

  int N, M;
  cin >> N >> K >> M;
  TournamentTree tt(N);
  for (int i=0; i<N; ++i) {
    int val;
    cin >> val;
    tt.update(i+1, val, true);
  }
  tt.build();

  repeat (M) {
    int type;
    cin >> type;
    if (type == 1) {
      int p, v;
      cin >> p >> v;
      tt.update(p, v, false);
    } else if (type == 2) {
      int ans = tt.query();
      cout << (ans <= N ? ans : -1) << '\n';
    }
  }
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 5844 KB Output is correct
2 Correct 7 ms 5844 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 7252 KB Output is correct
2 Correct 9 ms 7252 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 8456 KB Output is correct
2 Correct 12 ms 8404 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 33612 KB Output is correct
2 Correct 277 ms 115148 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 88976 KB Output is correct
2 Correct 326 ms 154020 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1014 ms 67844 KB Output is correct
2 Correct 329 ms 132936 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1190 ms 106880 KB Output is correct
2 Correct 423 ms 139440 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1239 ms 99224 KB Output is correct
2 Correct 374 ms 147756 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1481 ms 163444 KB Output is correct
2 Correct 356 ms 163164 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1427 ms 163140 KB Output is correct
2 Correct 345 ms 163160 KB Output is correct