結果

問題 No.2901 Logical Sum of Substring
ユーザー vjudge1vjudge1
提出日時 2024-09-25 20:20:18
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 301 ms / 3,000 ms
コード長 2,685 bytes
コンパイル時間 2,742 ms
コンパイル使用メモリ 163,908 KB
実行使用メモリ 86,400 KB
最終ジャッジ日時 2024-09-25 20:20:29
合計ジャッジ時間 10,497 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
47,232 KB
testcase_01 AC 33 ms
47,104 KB
testcase_02 AC 34 ms
47,104 KB
testcase_03 AC 34 ms
47,104 KB
testcase_04 AC 33 ms
47,104 KB
testcase_05 AC 35 ms
46,976 KB
testcase_06 AC 35 ms
47,104 KB
testcase_07 AC 34 ms
47,104 KB
testcase_08 AC 275 ms
86,400 KB
testcase_09 AC 269 ms
86,400 KB
testcase_10 AC 242 ms
86,400 KB
testcase_11 AC 288 ms
86,400 KB
testcase_12 AC 297 ms
86,400 KB
testcase_13 AC 267 ms
86,400 KB
testcase_14 AC 294 ms
86,400 KB
testcase_15 AC 264 ms
86,272 KB
testcase_16 AC 301 ms
86,400 KB
testcase_17 AC 242 ms
86,272 KB
testcase_18 AC 272 ms
86,144 KB
testcase_19 AC 256 ms
86,272 KB
testcase_20 AC 286 ms
86,400 KB
testcase_21 AC 251 ms
86,400 KB
testcase_22 AC 257 ms
86,400 KB
testcase_23 AC 232 ms
86,272 KB
testcase_24 AC 237 ms
86,272 KB
testcase_25 AC 263 ms
86,400 KB
testcase_26 AC 224 ms
83,328 KB
testcase_27 AC 220 ms
83,200 KB
testcase_28 AC 220 ms
83,328 KB
testcase_29 AC 224 ms
85,120 KB
testcase_30 AC 257 ms
84,992 KB
testcase_31 AC 219 ms
85,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MAXN = 200001;

int k;

struct INFO {
  int ans, len;
  vector<pii> pre, suf;
  INFO operator+(const INFO &x) {
    INFO ret;
    ret.ans = min(ans, x.ans);
    ret.len = len + x.len;
    for(auto [v, l] : suf) {
      for(auto [v2, l2] : x.pre) {
        if((v | v2) == (1 << k) - 1) {
          ret.ans = min(ret.ans, l + l2);
        }
      }
    }
    ret.pre = pre;
    for(auto [v, l] : x.pre) {
      if(((ret.pre.empty() ? 0 : ret.pre.back().first) | v) != (ret.pre.empty() ? 0 : ret.pre.back().first)) {
        ret.pre.emplace_back(((ret.pre.empty() ? 0 : ret.pre.back().first) | v), len + l);
      }
    }
    ret.suf = x.suf;
    for(auto [v, l] : suf) {
      if(((ret.suf.empty() ? 0 : int(ret.suf.back().first)) | v) != (ret.suf.empty() ? 0 : ret.suf.back().first)) {
        ret.suf.emplace_back(((ret.suf.empty() ? 0 : ret.suf.back().first) | v), x.len + l);
      }
    }
    return ret;
  }
};

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2], a[MAXN];
  INFO v[MAXN << 2];
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t;
    if(s == t) {
      v[u].ans = (a[s] == (1 << k) - 1 ? 1 : MAXN);
      v[u].len = 1;
      if(a[s]) {
        v[u].pre.emplace_back(a[s], 1);
        v[u].suf.emplace_back(a[s], 1);
      }
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
    v[u] = v[u << 1] + v[(u << 1) | 1];
  }
  void update(int u, int p, int x) {
    if(l[u] == r[u]) {
      v[u].ans = (x == (1 << k) - 1 ? 1 : MAXN);
      v[u].pre.clear(), v[u].suf.clear();
      if(x) {
        v[u].pre.emplace_back(x, 1);
        v[u].suf.emplace_back(x, 1);
      }
      return;
    }
    (p <= r[u << 1] ? update(u << 1, p, x) : update((u << 1) | 1, p, x));
    v[u] = v[u << 1] + v[(u << 1) | 1];
  }
  INFO GetINFO(int u, int s, int t) {
    if(l[u] >= s && r[u] <= t) {
      return v[u];
    }
    if(s <= r[u << 1] && t >= l[(u << 1) | 1]) {
      return GetINFO(u << 1, s, t) + GetINFO((u << 1) | 1, s, t);
    }else if(t <= r[u << 1]) {
      return GetINFO(u << 1, s, t);
    }else {
      return GetINFO((u << 1) | 1, s, t);
    }
  }
}tr;

int n, q;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> tr.a[i];
  }
  tr.build(1, 1, n);
  cin >> q;
  for(int i = 1, op, p, x, l, r; i <= q; ++i) {
    cin >> op;
    if(op == 1) {
      cin >> p >> x;
      tr.update(1, p, x);
    }else {
      cin >> l >> r;
      int ans = tr.GetINFO(1, l, r).ans;
      cout << (ans == MAXN ? -1 : ans) << "\n";
    }
  }
  return 0;
}
0