oj.uz

Submission #750993

# Submission time Handle Problem Language Result Execution time Memory
750993 2023-05-30T18:10:15 Z sysia Crossing (JOI21_crossing) C++17
100 / 100
 480 ms 101008 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void add(int &a, int b){
    a += b;
    if (a >= mod) a-=mod;
}

int add2(int a, int b){
    add(a, b);
    return a;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(int a, int b){
    return (a*b)%mod;
}

T f(T a, T b){
    return T{add2(a.first, b.first), add2(a.second, b.second)};
}

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
    return a + rng()%(b-a+1);
}
/*
struct Tree{
    vector<T>tab;
    int size = 1;

    Tree(int n, string&s){
        while (size < n) size*=2;
        tab.assign(2*size, {0, 0});
    }

    void update(int x, T v){
        x += size;
        tab[x] = v;
        while (x){
            x/=2;
            tab[x] = f(tab[2*x], tab[2*x+1]);
        }
    }

    T query(int l, int r){
        T ans = {0, 0};
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) ans = f(ans, tab[l+1]);
            if (r&1) ans = f(ans, tab[r-1]);
        }
        return ans;
    }
};
*/

set<vector<int>>now;
vector<int>A, B, C;

int change(char c){
    if (c == 'J') return 0;
    else if (c == 'O') return 1;
    return 2;
}

void gen(string s, vector<int>&a){
    for (auto c: s){
        a.emplace_back(change(c));
    }
}

vector<int> merge(vector<int>&a, vector<int>&b){
    vector<int>ret;
    for (int i = 0; i<(int)a.size(); i++){
        ret.emplace_back((2*a[i] + 2*b[i])%3);
    }
    return ret;
}

struct Q{
    int l, r, c;
    T h;
    Q(){}
    Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
    bool operator <(const Q&he) const {
        return l < he.l;
    }
};

void rec(vector<int>s){
    if (now.find(s) != now.end()) return;
    now.insert(s);
    for (auto t: {A, B, C}){
        rec(merge(s, t));
    }
}

int sub2(int a, int b){
    sub(a, b);
    return a;
}

T fsub(T a, T b){
    return {sub2(a.first, b.first), sub2(a.second, b.second)};
}

void solve(){
    int n; cin >> n;
    string a, b, c; cin >> a >> b >> c;
    gen(a, A);
    gen(b, B);
    gen(c, C);
    for (auto s: {A, B, C}) rec(s);
    assert((int)now.size() <= 9);
    vector<T>Hash;
    int b1 = p(1, mod-1), b2 = p(1, mod-1);
    T p = {1, 1};
    for (auto vt: now){
        T H = {0, 0};
        // debug(vt);
        p = {1, 1};
        for (auto ch: vt){
            H = f(H, {mul(ch, p.first), mul(ch, p.second)});
            p = {mul(p.first, b1), mul(p.second, b2)};
            // debug(H);
        }
        Hash.emplace_back(H);
    }
    int q; cin >> q >> a;
    A.clear(); gen(a, A);
    set<Q>blocks;
    int begin = 0;
    T sum = {0, 0}, all = {0, 0};
    p = {1, 1};
    for (int i = 0; i<n; i++){
        if (i && A[i] != A[i-1]){
            blocks.insert({begin, i-1, sum, A[i-1]});  
            begin = i;
            sum = {0, 0};
        } 
        sum = f(sum, {mul(A[i], p.first), mul(A[i], p.second)});
        all = f(all, {mul(A[i], p.first), mul(A[i], p.second)});
        p = {mul(p.first, b1), mul(p.second, b2)};
    }
    blocks.insert({begin, n-1, sum, A.back()});
    // for (auto [l, r, h, c]: blocks){
    //     debug(l, r, h, c);
    // }
    auto answer = [&](){
        for (auto x: Hash){
            if (x == all){
                cout << "Yes\n";
                return;
            }
        }
        cout << "No\n";
    };
    debug(all);
    answer();

    vector<int>power1(n+1), power2(n+1);
    vector<int>pref1(n+1), pref2(n+1);
    power1[0] = power2[0] = 1;
    pref1[0] = pref2[0] = 1;
    for (int i = 1; i<=n; i++){
        power1[i] = mul(power1[i-1], b1);
        power2[i] = mul(power2[i-1], b2);
        pref1[i] = add2(pref1[i-1], power1[i]);
        pref2[i] = add2(pref2[i-1], power2[i]);
    }
    auto get_sum = [&](int l, int r, int v)->T {
        if (r < l) return T{0ll, 0ll};
        T ret;
        ret.first = mul(power1[l], mul(v, pref1[r-l]));
        ret.second = mul(power2[l], mul(v, pref2[r-l]));
        return ret;
    };

    while (q--){
        int l, r; char d; cin >> l >> r >> d;
        --l;--r;
        debug(l, r, d);
        int what = change(d);
        auto wrr = prev(blocks.upper_bound({l, -oo, {-oo, -oo}, -oo}));
        vector<Q>change;
        vector<int>fix;
        for (auto it = wrr; it != blocks.end() && it->l <= r; it++){
            auto [ll, rr, val, hh] = *it;
            fix.emplace_back(ll);
            // debug(ll, rr, val, hh);
            if (ll >= l && rr <= r){
                all = fsub(all, hh);
            } else {
                //at most two such intervals
                bool sub = 0;
                if (ll < l){
                    change.emplace_back(ll, l-1, get_sum(ll, l-1, val), val);
                    all = fsub(all, get_sum(l, min(rr, r), val));
                    sub = 1;
                }
                if (rr > r){
                    change.emplace_back(r+1, rr, get_sum(r+1, rr, val), val);
                    if (!sub){
                        all = fsub(all, get_sum(max(ll, l), r, val));
                    }
                }
            }
        }
        debug(all);
        change.emplace_back(l, r, get_sum(l, r, what), what);
        for (auto x: fix){
            blocks.erase(blocks.lower_bound({x, -oo, {-oo, -oo}, -oo}));
        }
        all = f(all, get_sum(l, r, what));
        for (auto x: change) {
            blocks.insert(x);
        }
        // for (auto [l, r, val, hh]: blocks){
        //     debug(l, r, val, hh);
        // }
        debug(all);
        answer();
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Compilation message

Main.cpp: In constructor 'Q::Q(long long int, long long int, T, long long int)':
Main.cpp:114:7: warning: 'Q::h' will be initialized after [-Wreorder]
  114 |     T h;
      |       ^
Main.cpp:113:15: warning:   'long long int Q::c' [-Wreorder]
  113 |     int l, r, c;
      |               ^
Main.cpp:116:5: warning:   when initialized here [-Wreorder]
  116 |     Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
      |     ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 804 KB Output is correct
2 Correct 159 ms 816 KB Output is correct
3 Correct 124 ms 904 KB Output is correct
4 Correct 150 ms 860 KB Output is correct
5 Correct 127 ms 844 KB Output is correct
6 Correct 131 ms 868 KB Output is correct
7 Correct 135 ms 952 KB Output is correct
8 Correct 133 ms 840 KB Output is correct
9 Correct 163 ms 828 KB Output is correct
10 Correct 138 ms 868 KB Output is correct
11 Correct 145 ms 996 KB Output is correct
12 Correct 139 ms 936 KB Output is correct
13 Correct 155 ms 832 KB Output is correct
14 Correct 137 ms 936 KB Output is correct
15 Correct 137 ms 892 KB Output is correct
16 Correct 137 ms 928 KB Output is correct
17 Correct 146 ms 924 KB Output is correct
18 Correct 115 ms 928 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 804 KB Output is correct
2 Correct 159 ms 816 KB Output is correct
3 Correct 124 ms 904 KB Output is correct
4 Correct 150 ms 860 KB Output is correct
5 Correct 127 ms 844 KB Output is correct
6 Correct 131 ms 868 KB Output is correct
7 Correct 135 ms 952 KB Output is correct
8 Correct 133 ms 840 KB Output is correct
9 Correct 163 ms 828 KB Output is correct
10 Correct 138 ms 868 KB Output is correct
11 Correct 145 ms 996 KB Output is correct
12 Correct 139 ms 936 KB Output is correct
13 Correct 155 ms 832 KB Output is correct
14 Correct 137 ms 936 KB Output is correct
15 Correct 137 ms 892 KB Output is correct
16 Correct 137 ms 928 KB Output is correct
17 Correct 146 ms 924 KB Output is correct
18 Correct 115 ms 928 KB Output is correct
19 Correct 302 ms 24940 KB Output is correct
20 Correct 266 ms 26344 KB Output is correct
21 Correct 380 ms 25040 KB Output is correct
22 Correct 378 ms 23240 KB Output is correct
23 Correct 206 ms 2252 KB Output is correct
24 Correct 201 ms 2176 KB Output is correct
25 Correct 375 ms 27468 KB Output is correct
26 Correct 434 ms 26956 KB Output is correct
27 Correct 237 ms 24928 KB Output is correct
28 Correct 247 ms 24928 KB Output is correct
29 Correct 229 ms 24344 KB Output is correct
30 Correct 180 ms 1868 KB Output is correct
31 Correct 272 ms 24928 KB Output is correct
32 Correct 263 ms 22968 KB Output is correct
33 Correct 218 ms 2096 KB Output is correct
34 Correct 315 ms 26960 KB Output is correct
35 Correct 391 ms 20608 KB Output is correct
36 Correct 211 ms 2180 KB Output is correct
37 Correct 206 ms 2172 KB Output is correct
38 Correct 224 ms 26484 KB Output is correct
39 Correct 271 ms 24876 KB Output is correct
40 Correct 373 ms 18216 KB Output is correct
41 Correct 303 ms 26880 KB Output is correct
42 Correct 129 ms 26960 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 804 KB Output is correct
2 Correct 159 ms 816 KB Output is correct
3 Correct 124 ms 904 KB Output is correct
4 Correct 150 ms 860 KB Output is correct
5 Correct 127 ms 844 KB Output is correct
6 Correct 131 ms 868 KB Output is correct
7 Correct 135 ms 952 KB Output is correct
8 Correct 133 ms 840 KB Output is correct
9 Correct 163 ms 828 KB Output is correct
10 Correct 138 ms 868 KB Output is correct
11 Correct 145 ms 996 KB Output is correct
12 Correct 139 ms 936 KB Output is correct
13 Correct 155 ms 832 KB Output is correct
14 Correct 137 ms 936 KB Output is correct
15 Correct 137 ms 892 KB Output is correct
16 Correct 137 ms 928 KB Output is correct
17 Correct 146 ms 924 KB Output is correct
18 Correct 115 ms 928 KB Output is correct
19 Correct 153 ms 908 KB Output is correct
20 Correct 133 ms 872 KB Output is correct
21 Correct 132 ms 1028 KB Output is correct
22 Correct 122 ms 860 KB Output is correct
23 Correct 142 ms 844 KB Output is correct
24 Correct 149 ms 1008 KB Output is correct
25 Correct 141 ms 860 KB Output is correct
26 Correct 131 ms 840 KB Output is correct
27 Correct 135 ms 812 KB Output is correct
28 Correct 126 ms 872 KB Output is correct
29 Correct 136 ms 928 KB Output is correct
30 Correct 141 ms 904 KB Output is correct
31 Correct 151 ms 840 KB Output is correct
32 Correct 133 ms 872 KB Output is correct
33 Correct 142 ms 948 KB Output is correct
34 Correct 148 ms 864 KB Output is correct
35 Correct 139 ms 864 KB Output is correct
36 Correct 142 ms 916 KB Output is correct
37 Correct 151 ms 964 KB Output is correct
38 Correct 136 ms 948 KB Output is correct
39 Correct 140 ms 952 KB Output is correct
40 Correct 156 ms 972 KB Output is correct
41 Correct 137 ms 896 KB Output is correct
42 Correct 158 ms 1068 KB Output is correct
43 Correct 134 ms 944 KB Output is correct
44 Correct 140 ms 956 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 804 KB Output is correct
2 Correct 159 ms 816 KB Output is correct
3 Correct 124 ms 904 KB Output is correct
4 Correct 150 ms 860 KB Output is correct
5 Correct 127 ms 844 KB Output is correct
6 Correct 131 ms 868 KB Output is correct
7 Correct 135 ms 952 KB Output is correct
8 Correct 133 ms 840 KB Output is correct
9 Correct 163 ms 828 KB Output is correct
10 Correct 138 ms 868 KB Output is correct
11 Correct 145 ms 996 KB Output is correct
12 Correct 139 ms 936 KB Output is correct
13 Correct 155 ms 832 KB Output is correct
14 Correct 137 ms 936 KB Output is correct
15 Correct 137 ms 892 KB Output is correct
16 Correct 137 ms 928 KB Output is correct
17 Correct 146 ms 924 KB Output is correct
18 Correct 115 ms 928 KB Output is correct
19 Correct 302 ms 24940 KB Output is correct
20 Correct 266 ms 26344 KB Output is correct
21 Correct 380 ms 25040 KB Output is correct
22 Correct 378 ms 23240 KB Output is correct
23 Correct 206 ms 2252 KB Output is correct
24 Correct 201 ms 2176 KB Output is correct
25 Correct 375 ms 27468 KB Output is correct
26 Correct 434 ms 26956 KB Output is correct
27 Correct 237 ms 24928 KB Output is correct
28 Correct 247 ms 24928 KB Output is correct
29 Correct 229 ms 24344 KB Output is correct
30 Correct 180 ms 1868 KB Output is correct
31 Correct 272 ms 24928 KB Output is correct
32 Correct 263 ms 22968 KB Output is correct
33 Correct 218 ms 2096 KB Output is correct
34 Correct 315 ms 26960 KB Output is correct
35 Correct 391 ms 20608 KB Output is correct
36 Correct 211 ms 2180 KB Output is correct
37 Correct 206 ms 2172 KB Output is correct
38 Correct 224 ms 26484 KB Output is correct
39 Correct 271 ms 24876 KB Output is correct
40 Correct 373 ms 18216 KB Output is correct
41 Correct 303 ms 26880 KB Output is correct
42 Correct 129 ms 26960 KB Output is correct
43 Correct 153 ms 908 KB Output is correct
44 Correct 133 ms 872 KB Output is correct
45 Correct 132 ms 1028 KB Output is correct
46 Correct 122 ms 860 KB Output is correct
47 Correct 142 ms 844 KB Output is correct
48 Correct 149 ms 1008 KB Output is correct
49 Correct 141 ms 860 KB Output is correct
50 Correct 131 ms 840 KB Output is correct
51 Correct 135 ms 812 KB Output is correct
52 Correct 126 ms 872 KB Output is correct
53 Correct 136 ms 928 KB Output is correct
54 Correct 141 ms 904 KB Output is correct
55 Correct 151 ms 840 KB Output is correct
56 Correct 133 ms 872 KB Output is correct
57 Correct 142 ms 948 KB Output is correct
58 Correct 148 ms 864 KB Output is correct
59 Correct 139 ms 864 KB Output is correct
60 Correct 142 ms 916 KB Output is correct
61 Correct 151 ms 964 KB Output is correct
62 Correct 136 ms 948 KB Output is correct
63 Correct 140 ms 952 KB Output is correct
64 Correct 156 ms 972 KB Output is correct
65 Correct 137 ms 896 KB Output is correct
66 Correct 158 ms 1068 KB Output is correct
67 Correct 134 ms 944 KB Output is correct
68 Correct 140 ms 956 KB Output is correct
69 Correct 336 ms 86012 KB Output is correct
70 Correct 337 ms 100196 KB Output is correct
71 Correct 209 ms 3044 KB Output is correct
72 Correct 207 ms 3044 KB Output is correct
73 Correct 205 ms 3016 KB Output is correct
74 Correct 431 ms 37300 KB Output is correct
75 Correct 205 ms 2956 KB Output is correct
76 Correct 424 ms 43908 KB Output is correct
77 Correct 346 ms 37400 KB Output is correct
78 Correct 202 ms 2984 KB Output is correct
79 Correct 215 ms 3032 KB Output is correct
80 Correct 350 ms 72184 KB Output is correct
81 Correct 201 ms 5736 KB Output is correct
82 Correct 480 ms 100260 KB Output is correct
83 Correct 427 ms 94776 KB Output is correct
84 Correct 203 ms 5748 KB Output is correct
85 Correct 210 ms 5816 KB Output is correct
86 Correct 326 ms 76716 KB Output is correct
87 Correct 369 ms 100276 KB Output is correct
88 Correct 197 ms 5928 KB Output is correct
89 Correct 351 ms 89804 KB Output is correct
90 Correct 368 ms 100292 KB Output is correct
91 Correct 205 ms 5748 KB Output is correct
92 Correct 437 ms 75620 KB Output is correct
93 Correct 210 ms 5808 KB Output is correct
94 Correct 224 ms 5764 KB Output is correct
95 Correct 206 ms 5844 KB Output is correct
96 Correct 173 ms 24912 KB Output is correct
97 Correct 356 ms 100188 KB Output is correct
98 Correct 420 ms 66048 KB Output is correct
99 Correct 337 ms 101008 KB Output is correct
100 Correct 196 ms 100960 KB Output is correct