結果

問題 No.1439 Let's Compare!!!!
ユーザー sten_sansten_san
提出日時 2021-03-26 21:51:26
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 615 ms / 2,000 ms
コード長 2,552 bytes
コンパイル時間 2,841 ms
コンパイル使用メモリ 200,872 KB
実行使用メモリ 8,648 KB
最終ジャッジ日時 2023-08-19 15:17:07
合計ジャッジ時間 7,622 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge10
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,952 KB
testcase_01 AC 4 ms
8,100 KB
testcase_02 AC 4 ms
8,328 KB
testcase_03 AC 4 ms
7,968 KB
testcase_04 AC 5 ms
8,224 KB
testcase_05 AC 4 ms
8,140 KB
testcase_06 AC 4 ms
8,048 KB
testcase_07 AC 9 ms
8,340 KB
testcase_08 AC 13 ms
7,984 KB
testcase_09 AC 7 ms
8,064 KB
testcase_10 AC 304 ms
8,532 KB
testcase_11 AC 451 ms
8,584 KB
testcase_12 AC 439 ms
8,604 KB
testcase_13 AC 305 ms
8,644 KB
testcase_14 AC 302 ms
8,616 KB
testcase_15 AC 563 ms
8,512 KB
testcase_16 AC 609 ms
8,584 KB
testcase_17 AC 615 ms
8,648 KB
testcase_18 AC 468 ms
8,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct iofast_t {
    iofast_t() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); cout.tie(nullptr);
    }
} iofast;

struct uns_t {} uns;
template <typename Element, typename Head, typename ...Args>
auto vec(Element init, Head arg, Args ...args) {
    if constexpr (sizeof...(Args) == 0) return std::vector(arg, init);
    else return std::vector(arg, vec(init, args...));
}
template <typename Element, typename Head, typename ...Args>
auto vec(uns_t, Head arg, Args ...args) {
    return vec(Element(), arg, args...);
}

template <typename T, typename Compare = less<T>>
T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }
template <typename T, typename Compare = less<T>>
T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }

array<int, 4 * 100000> upper1, upper2;
array<int, 4 * 100000> under;
int bucket_size;

//  0: upper1 = upper2
// +1: upper1 < upper2
// -1: upper1 > upper2
void compare(int bucket) {
    int ans = 0;
    for (int i = bucket * bucket_size; i < (bucket + 1) * bucket_size && ans == 0; ++i) {
        if (upper1[i] < upper2[i]) {
            ans = +1;
        }
        if (upper1[i] > upper2[i]) {
            ans = -1;
        }
    }
    under[bucket] = ans;
}

void init(int n, string s, string t) {
    fill(begin(upper1), end(upper1), 0);
    fill(begin(upper2), end(upper2), 0);
    fill(begin(under), end(under), 0);

    bucket_size = sqrt(n);
    for (int i = 0; i < n; ++i) {
        upper1[i] = s[i] - '0';
        upper2[i] = t[i] - '0';
    }

    compare(0);
    for (int i = 1; i <= n / i; ++i) {
        compare(i);
    }
}

// upper1
void set1(int i, int x) {
    upper1[i] = x;
    compare(i / bucket_size);
}

// upper2
void set2(int i, int x) {
    upper2[i] = x;
    compare(i / bucket_size);
}

int query(int n) {
    int ans = under[0];
    for (int i = 1; i <= n / i && ans == 0; ++i) {
        ans = under[i];
    }
    return ans;
}

int main() {
    int n; cin >> n;
    string s, t; cin >> s >> t;

    init(n, s, t);

    int q; cin >> q;
    while (q--) {
        char type; cin >> type;
        int x, y; cin >> x >> y;
        if (type == 'S') {
            set1(x - 1, y);
        }
        if (type == 'T') {
            set2(x - 1, y);
        }

        auto ans = query(n);
        if (ans == 0) {
            cout << "=" << endl;
        }
        if (ans < 0) {
            cout << ">" << endl;
        }
        if (ans > 0) {
            cout << "<" << endl;
        }
    }
}
0