結果
問題 | No.2080 Simple Nim Query |
ユーザー | outline |
提出日時 | 2022-10-13 16:45:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 285 ms / 3,000 ms |
コード長 | 4,787 bytes |
コンパイル時間 | 1,408 ms |
コンパイル使用メモリ | 140,404 KB |
実行使用メモリ | 6,144 KB |
最終ジャッジ日時 | 2024-06-12 07:29:15 |
合計ジャッジ時間 | 3,712 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 46 ms
5,376 KB |
testcase_04 | AC | 46 ms
5,376 KB |
testcase_05 | AC | 95 ms
5,888 KB |
testcase_06 | AC | 285 ms
6,144 KB |
testcase_07 | AC | 280 ms
6,144 KB |
testcase_08 | AC | 127 ms
6,016 KB |
testcase_09 | AC | 124 ms
6,016 KB |
testcase_10 | AC | 279 ms
6,144 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <string> #include <map> #include <set> #include <stack> #include <tuple> #include <deque> #include <array> #include <numeric> #include <bitset> #include <iomanip> #include <cassert> #include <chrono> #include <random> #include <limits> #include <iterator> #include <functional> #include <sstream> #include <fstream> #include <complex> #include <cstring> #include <unordered_map> #include <unordered_set> using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") using ll = long long; constexpr int INF = 1001001001; // constexpr int mod = 1000000007; constexpr int mod = 998244353; template<class T> inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template<class T> inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; template<typename Monoid> struct SegmentTree{ using F = function<Monoid(Monoid, Monoid)>; int sz; vector<Monoid> seg; const F f; const Monoid M1; SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {} SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void resize(int n){ sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x){ seg[k + sz] = x; } void build(){ for(int k = sz - 1; k > 0; --k){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } void update(int k, const Monoid &x){ k += sz; seg[k] = x; while(k >>= 1){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } Monoid query(int a, int b){ Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const{ return seg[k + sz]; } // (type = true) : find_last // (type = false) : find_first template<typename C> int find_subtree(int a, const C &check, Monoid &M, bool type){ while(a < sz){ Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]); if(check(nxt)) a = a << 1 | type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template<typename C> int find_first(int a, const C &check){ Monoid L = M1; if(a <= 0){ if(check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1){ Monoid nxt = f(L, seg[a]); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template<typename C> int find_last(int b, const C &check){ Monoid R = M1; if(b >= sz){ if(check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1){ if(b & 1){ Monoid nxt = f(seg[--b], R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<int> A(N); for(int i = 0; i < N; ++i) cin >> A[i]; auto f = [](int l, int r) { return l + r; }; SegmentTree<int> seg(N, f, 0); for(int i = 0; i < N; ++i){ seg.set(i, A[i] == 1); } seg.build(); for(int q = 0; q < Q; ++q){ int T, X, Y; cin >> T >> X >> Y; --X; if(T == 1){ A[X] = Y; seg.update(X, Y == 1); } else{ if(Y - X == 1 || A[Y - 1] > 1){ cout << "F\n"; continue; } int l = X, r = Y - 1; while(r - l > 1){ int m = (l + r) / 2; (seg.query(m, Y) == Y - m ? r : l) = m; } cout << (seg.query(r, Y) % 2 == 0 ? "F\n" : "S\n"); } } return 0; }