oj.uz

답안 #648067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648067 2022-10-05T09:18:38 Z Shin Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 1605 ms 416524 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

long long target;
const int offset = (1 << 17) + 7;
struct segment_tree {
  struct node {
    pair<long long, int> pref[50], suff[50];
    int best;
    int len;
    int p_sz, s_sz;
    node() {
      len = p_sz = s_sz = 0;
      best = (int) 1e9;
    }
    node(long long v) {
      len = p_sz = s_sz = 1;
      best = (v == target ? 1 : (int) 1e9);
      pref[0] = suff[0] = mp(v, 1);
    }
    void add_pref(pair<long long, int> x) {
      pref[p_sz ++] = x;
    }
    void add_suff(pair<long long, int> x) {
      suff[s_sz ++] = x;
    }
    #define new_bit(s1, s2) ((s1 | s2) != s1)
    friend node operator + (node &a, node &b) {
      node res;
      for (int i = 0; i < a.p_sz; i ++) {
        res.add_pref(a.pref[i]);
      }
      for (int i = 0; i < b.s_sz; i ++) {
        res.add_suff(b.suff[i]);
      }
      long long mask = a.pref[a.p_sz - 1].fi;
      for (int i = 0; i < b.p_sz; i ++) {
        if (!new_bit(mask, b.pref[i].fi)) {
          continue;
        }
        mask |= b.pref[i].fi;
        res.add_pref(mp(mask, a.len + b.pref[i].se));
      }
      mask = b.suff[b.s_sz - 1].fi;
      for (int i = 0; i < a.s_sz; i ++) {
        if (!new_bit(mask, a.suff[i].fi)) {
          continue;
        }
        mask |= a.suff[i].fi;
        res.add_suff(mp(mask, b.len + a.suff[i].se));
      }
      for (int i = a.s_sz - 1, j = 0; ~i; i --) {
        while (j < b.p_sz && (a.suff[i].fi | b.pref[j].fi) != target) {
          j ++;
        }
        if (j == b.p_sz || (a.suff[i].fi | b.pref[j].fi) != target) {
          break;
        }
        minimize(res.best, a.suff[i].se + b.pref[j].se);
      }
      minimize(res.best, min(a.best, b.best));
      res.len = a.len + b.len;
      return res;
    }
    #undef new_bit
  };
  node t[offset << 1];

  void modify(int p, long long v) {
    p += offset;
    t[p] = node(v);
    for (int i = p / 2; i; i >>= 1) {
      t[i] = t[i << 1] + t[i << 1 | 1];
    }
  }

  int get_ans() {
    return t[1].best == (int) 1e9 ? -1 : t[1].best;
  }
} st;

const int N = 1e5 + 7;
int n, m, k, q;
int a[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> q;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
    a[i] --;
  }
  target = (1LL << k) - 1;
  for (int i = 1; i <= n; i ++) {
    st.modify(i, 1LL << a[i]);
  }
  while (q --) {
    int t; cin >> t;
    if (t == 2) {
      cout << st.get_ans() << '\n';
    } else {
      int p, v; cin >> p >> v;
      v --;
      st.modify(p, 1LL << v);
    }
  }
  return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 414796 KB Output is correct
2 Correct 215 ms 414884 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 414868 KB Output is correct
2 Correct 252 ms 414820 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 414976 KB Output is correct
2 Correct 237 ms 414884 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 587 ms 415408 KB Output is correct
2 Correct 1327 ms 416116 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 914 ms 415776 KB Output is correct
2 Correct 1382 ms 416496 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1132 ms 415864 KB Output is correct
2 Correct 1359 ms 416324 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 416012 KB Output is correct
2 Correct 1405 ms 416324 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1174 ms 415968 KB Output is correct
2 Correct 1448 ms 416452 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1605 ms 416356 KB Output is correct
2 Correct 1482 ms 416488 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1566 ms 416304 KB Output is correct
2 Correct 1461 ms 416524 KB Output is correct