oj.uz

답안 #648026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648026 2022-10-05T03:28:34 Z Shin Nekameleoni (COCI15_nekameleoni) C++14
70 / 140
 1403 ms 524288 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;
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) {
      assert(p_sz <= 50);
      pref[p_sz ++] = x;
    }
    void add_suff(pair<long long, int> x) {
      assert(s_sz <= 50);
      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
  };

  vector<node> t;
  int n;

  segment_tree(int _n) : n(_n) {
    t.resize((n << 2) + 7);
  }

  void modify(int id, int l, int r, int p, long long v) {
    if (l > p || r < p) {
      return;
    }
    if (l == r) {
      t[id] = node(v);
    } else {
      int mid = (l + r) >> 1;
      modify(id << 1, l, mid, p, v);
      modify(id << 1 | 1, mid + 1, r, p, v);
      t[id] = t[id << 1] + t[id << 1 | 1];
    }
  }

  void out(int id) {
    for (int i = 0; i < t[id].s_sz; i ++) {
      cout << t[id].suff[i].fi << " " << t[id].suff[i].se << '\n';
    }
  }
  void modify(int p, long long v) {
    modify(1, 1, n, p, v);
  }

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

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;
  segment_tree st(n);
  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 30 ms 21972 KB Output is correct
2 Correct 29 ms 21972 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 27604 KB Output is correct
2 Correct 44 ms 27592 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 32004 KB Output is correct
2 Correct 64 ms 31956 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 130072 KB Output is correct
2 Correct 1257 ms 447212 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 885 ms 345348 KB Output is correct
2 Runtime error 234 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 892 ms 263536 KB Output is correct
2 Correct 1403 ms 516980 KB Output is correct

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1188 ms 415496 KB Output is correct
2 Runtime error 227 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1178 ms 384444 KB Output is correct
2 Runtime error 227 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 232 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 238 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -