結果

問題 No.2901 Logical Sum of Substring
コンテスト
ユーザー solstice
提出日時 2026-01-11 11:06:13
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 7,098 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,988 ms
コンパイル使用メモリ 379,532 KB
実行使用メモリ 20,824 KB
最終ジャッジ日時 2026-01-11 11:06:26
合計ジャッジ時間 12,101 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// suo
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
// #include "atcoder/segtree.hpp"
// using namespace atcoder;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<pair<int,int>, null_type, greater<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;  

typedef long long ll;
typedef long double ld;
using usize = size_t;
using NAME = void;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

template<class qu> using pq = priority_queue<qu>;
template<class qu> using pqg = priority_queue<qu, vector<qu>, greater<qu>>;

// #define mp make_pair
#define int long long
#define uint long long
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define fi first
#define se second
#define lso(s) ((s) & -(s))
int lg(ll s) { return s ? __builtin_clzll(1) - __builtin_clzll(s) : -1; }//lg(1)=0, lg(2)=1, lg(3)=1, lg(4)=2, ...
#define all(x) begin(x), end(x)
// #define sz(x) (int)(x).sz()

const ll MOD = (int)1e9 + 7;
const ll mod = 998244353;
const double EPS = 1e-16;
const ll BIG = 1e18;
const ll INF = 4e18;
ll lcm(ll a,ll b) { return a/__gcd(a,b)*b; }
ll floor(ll a, ll b) { return a / b - (a % b < 0); }
ll ceil(ll a, ll b) { return a / b + (a % b > 0); }

template<typename qu>
istream& operator>>(istream& in, vector<qu> &vec){
  for(auto &x : vec){
    in >> x;
  }
  return in;
}

#ifdef sparkle
template <typename T>
ostream& operator << (ostream &o, vector<T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.a/splitmix64.c
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const noexcept {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  size_t operator()(const pair<ll, ll>& pq) const noexcept {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    uint64_t h1 = splitmix64((uint64_t)pq.first + FIXED_RANDOM);
    uint64_t h2 = splitmix64((uint64_t)pq.second + FIXED_RANDOM + 0x9e3779b97f4a7c15ULL);
    return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
  }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gen() {
  ll x = 0;
  while(x == 0)
    x = rng() % MOD;
  return x;
}

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}
  mint& operator-=(const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD;return *this;}
  mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}
  mint operator+(const mint a) const {mint res(*this);return res+=a;}
  mint operator-(const mint a) const {mint res(*this);return res-=a;}
  mint operator*(const mint a) const {mint res(*this);return res*=a;}
  mint pow(ll b) const {
      mint res(1), a(*this);
      while (b) {
          if (b & 1) res *= a;
          a *= a;
          b >>= 1;
      }
      return res;
  }
  // for pq MOD
  mint inv() const {return pow(MOD-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint operator/(const mint a) const {mint res(*this);return res/=a;}
};  
ostream& operator<<(ostream& os, const mint& a) {os << a.x; return os;}

template <class T>
  inline void chadd(T &x, T y) { x += y; if(x >= mod) x -= mod; }

template <class T>
  inline void chmin(T &x, T y) { if (y < x) x = y; }

template <class T>
  inline void chmax(T &x, T y) { if (y > x) x = y; }

auto mul(int a, int b) -> int { return (a % MOD * b % MOD) % MOD; }
auto add(int a, int b) -> int { return (a % MOD + b % MOD) % MOD; }
auto sub(int a, int b) -> int { return (a % MOD - b % MOD + MOD) % MOD; }

inline NAME  before() { }

// #define tests
auto sparkle() -> void {
  
}

struct ST {
  int n;
  vector<int> seg;
  ST(int _) {
    n = 1;
    while (n < _) n *= 2;
    seg.assign(4 * n, 0);
  }
  auto update(int i, int v) -> void {
    i += n;
    seg[i] = v;
    while (i > 1) {
      i /= 2;
      seg[i] = seg[2 * i] | seg[2 * i + 1];
    }
  }
  auto query(int l, int r) -> int {
    int res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) res |= seg[l++];
      if (r & 1) res |= seg[r++];
    }
    return res;
  }
};

[[gnu::target("avx2"), gnu::flatten]] 
auto main() -> int32_t {
  std::cin.tie(nullptr)->sync_with_stdio(0);
  std::cin.exceptions(std::ios::failbit | std::ios::badbit);
  // freopen("in","r",stdin);
  // freopen("outt","w",stdout);
  
  int TC = 1; // cin >> TC;
  while (TC --> 0) {  
    int n, k; cin >> n >> k;
    vector<int> a(n + 5);
    int pk = (1 << k) - 1;
    ST st(n + 5);
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      st.update(i, a[i]);
    }

    int q; cin >> q;
    while (q --> 0) {
      int op; cin >> op;
      if (op == 1) {
        int i, v; cin >> i >> v;
        a[i] = v;
        st.update(i, v);
      } else {
        int l, r; cin >> l  >> r;
        if (st.query(l, r + 1) != pk) {
          cout << "-1\n";
          continue;
        }
        int mn = BIG, rg = l;
        vector<int> cnt(k, 0);
        int cur = 0;

        auto add = [&](int x) {
          for (int i = 0; i < k; ++i) {
            if ((x >> i) & 1) {
              if (cnt[i] == 0) cur |= (1 << i);
              cnt[i]++;
            }
          }
        };
        auto remove = [&](int x) {
          for (int i = 0; i < k; ++i) {
            if ((x >> i) & 1) {
              cnt[i]--;
              if (cnt[i] == 0) cur &= ~(1 << i);
            }
          }
        };

        for (int lf = l; lf <= r; ++lf) {
          while (rg <= r and cur < pk) {
            add(a[rg]);
            rg++;
          }
          if (cur == pk) {
            mn = min(mn, rg - lf);
          }
          remove(a[lf]);
        }
        cout << (mn == BIG ? -1 : mn) << '\n';
      }
    }
  }
    
  return 0;
}
0