結果

問題 No.1439 Let's Compare!!!!
コンテスト
ユーザー sten_san
提出日時 2021-03-26 21:51:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 745 ms / 2,000 ms
コード長 2,552 bytes
コンパイル時間 2,907 ms
コンパイル使用メモリ 195,484 KB
最終ジャッジ日時 2025-01-19 22:25:26
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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