oj.uz

Submission #923011

# Submission time Handle Problem Language Result Execution time Memory
923011 2024-02-06T12:33:50 Z PagodePaiva Crossing (JOI21_crossing) C++17
3 / 100
 286 ms 21020 KB 
#include<bits/stdc++.h>
#define N 200010
#define int long long

using namespace std;

int n;
int pref[N][2];
const int p = 20673157;
const int q = 51491773;
int v[N];

struct Segtree{
    array <int, 2> tree[4*N];
    int lazy[4*N];

    array <int, 2> join(array <int, 2> a, array <int, 2> b){
        array <int, 2> res;
        res[0] = (a[0] + b[0]) % p;
        res[1] = (a[1] + b[1]) % q;
        return res;
    }

    void unlazy(int node, int l, int r){
        if(lazy[node] == -1) return;
        tree[node] = {(lazy[node]*(((pref[r][0] - pref[l-1][0]) % p + p) % p)) % p, (lazy[node]*(((pref[r][1] - pref[l-1][1]) % q + q) % q)) % q};
        lazy[2*node] = lazy[node];
        lazy[2*node+1] = lazy[node];
        lazy[node] = -1;
    }

    void build(int node, int l, int r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = {(v[l]*(((pref[l][0] - pref[l-1][0]) % p + p) % p)) % p, (v[l]*(((pref[l][1] - pref[l-1][1]) % q + q) % q)) % q};
            // cout << l << ' ' << r << ' ' << tree[node][0] << endl;
            return;    
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        // cout << l << ' ' << r << ' ' << tree[node][0] << endl;
        return;
    }

    void update(int node, int l, int r, int val, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(tl >= l and r >= tr){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, val, tl, mid);
        update(2*node+1, l, r, val, mid+1, tr);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }

    array <int, 2> query(int node, int l, int r, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {0, 0};
        if(tl >= l and r >= tr) return tree[node];
        int mid = (tl+tr)/2;
        return (join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr)));
    }
} seg;

array <int, 2> hasht(string st){
    array <int, 2> val = {0, 0};
    for(int i = 1;i <= n;i++){
        val[0] += ((((pref[i][0]-pref[i-1][0]) % p + p) % p)*(st[i-1] == 'J' ? 0 : (st[i-1] == 'O' ? 1 : 2))) % p;
        val[0] %= p;
        // cout << val[0] << ' ';
        // cout << st[i-1] << ' ';
        val[1] += ((((pref[i][1]-pref[i-1][1]) % q + q) % q)*(st[i-1] == 'J' ? 0 : (st[i-1] == 'O' ? 1 : 2))) % q;
        val[1] %= q;
    }
    // cout << endl;
    return val;
}

string st;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    cin >> st;
    cin >> st;
    cin >> st;
    pref[1][0] = 1;
    pref[1][1] = 1;
    int val1 = 1, val2 = 1;
    for(int i = 2;i <= n;i++){
        val1 *= 3;
        val1 %= p;
        val2 *= 3;
        val2 %= q;
        pref[i][0] = (val1 + pref[i-1][0]) % p;
        pref[i][1] = (val2 + pref[i-1][1]) % q;
    }
    array <int, 2> val = hasht(st);
    int qr;
    cin >> qr;
    string t;
    cin >> t;
    for(int i = 1;i <= n;i++){
        v[i] = (t[i-1] == 'J' ? 0 : (t[i-1] == 'O' ? 1 : 2));
    }
    seg.build(1, 1, n);
    // for(int i = 1;i <= n;i++) cout << seg.query(1, i, i, 1, n)[0] << ' ';
    // cout << seg.query(1, 1, n, 1, n)[0] << ' ' << seg.query(1,1, n, 1, n)[1] << endl;
    if(seg.query(1, 1, n, 1, n) == val){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
    // cout << val[0] << ' ' << val[1] << endl;
    while(qr--){
        int l, r;
        char c;
        cin >> l >> r;
        cin >> c;
        int x = (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
        seg.update(1, l, r, x, 1, n);
        // cout << seg.query(1, 1, n, 1, n)[0] << ' ' << seg.query(1, 1, n, 1, n)[1] << endl;
        if(seg.query(1, 1, n, 1, n) == val){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4944 KB Output is correct
2 Correct 73 ms 4948 KB Output is correct
3 Correct 75 ms 4948 KB Output is correct
4 Correct 54 ms 5132 KB Output is correct
5 Correct 55 ms 5012 KB Output is correct
6 Correct 55 ms 4956 KB Output is correct
7 Correct 56 ms 4948 KB Output is correct
8 Correct 58 ms 5088 KB Output is correct
9 Correct 59 ms 4956 KB Output is correct
10 Correct 70 ms 5044 KB Output is correct
11 Correct 59 ms 4920 KB Output is correct
12 Correct 58 ms 4944 KB Output is correct
13 Correct 59 ms 5124 KB Output is correct
14 Correct 58 ms 5072 KB Output is correct
15 Correct 60 ms 4952 KB Output is correct
16 Correct 58 ms 5068 KB Output is correct
17 Correct 59 ms 5188 KB Output is correct
18 Correct 69 ms 4948 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4944 KB Output is correct
2 Correct 73 ms 4948 KB Output is correct
3 Correct 75 ms 4948 KB Output is correct
4 Correct 54 ms 5132 KB Output is correct
5 Correct 55 ms 5012 KB Output is correct
6 Correct 55 ms 4956 KB Output is correct
7 Correct 56 ms 4948 KB Output is correct
8 Correct 58 ms 5088 KB Output is correct
9 Correct 59 ms 4956 KB Output is correct
10 Correct 70 ms 5044 KB Output is correct
11 Correct 59 ms 4920 KB Output is correct
12 Correct 58 ms 4944 KB Output is correct
13 Correct 59 ms 5124 KB Output is correct
14 Correct 58 ms 5072 KB Output is correct
15 Correct 60 ms 4952 KB Output is correct
16 Correct 58 ms 5068 KB Output is correct
17 Correct 59 ms 5188 KB Output is correct
18 Correct 69 ms 4948 KB Output is correct
19 Correct 286 ms 21016 KB Output is correct
20 Correct 249 ms 21020 KB Output is correct
21 Incorrect 146 ms 20724 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4944 KB Output is correct
2 Correct 73 ms 4948 KB Output is correct
3 Correct 75 ms 4948 KB Output is correct
4 Correct 54 ms 5132 KB Output is correct
5 Correct 55 ms 5012 KB Output is correct
6 Correct 55 ms 4956 KB Output is correct
7 Correct 56 ms 4948 KB Output is correct
8 Correct 58 ms 5088 KB Output is correct
9 Correct 59 ms 4956 KB Output is correct
10 Correct 70 ms 5044 KB Output is correct
11 Correct 59 ms 4920 KB Output is correct
12 Correct 58 ms 4944 KB Output is correct
13 Correct 59 ms 5124 KB Output is correct
14 Correct 58 ms 5072 KB Output is correct
15 Correct 60 ms 4952 KB Output is correct
16 Correct 58 ms 5068 KB Output is correct
17 Correct 59 ms 5188 KB Output is correct
18 Correct 69 ms 4948 KB Output is correct
19 Correct 66 ms 4948 KB Output is correct
20 Correct 75 ms 4944 KB Output is correct
21 Incorrect 59 ms 4948 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4944 KB Output is correct
2 Correct 73 ms 4948 KB Output is correct
3 Correct 75 ms 4948 KB Output is correct
4 Correct 54 ms 5132 KB Output is correct
5 Correct 55 ms 5012 KB Output is correct
6 Correct 55 ms 4956 KB Output is correct
7 Correct 56 ms 4948 KB Output is correct
8 Correct 58 ms 5088 KB Output is correct
9 Correct 59 ms 4956 KB Output is correct
10 Correct 70 ms 5044 KB Output is correct
11 Correct 59 ms 4920 KB Output is correct
12 Correct 58 ms 4944 KB Output is correct
13 Correct 59 ms 5124 KB Output is correct
14 Correct 58 ms 5072 KB Output is correct
15 Correct 60 ms 4952 KB Output is correct
16 Correct 58 ms 5068 KB Output is correct
17 Correct 59 ms 5188 KB Output is correct
18 Correct 69 ms 4948 KB Output is correct
19 Correct 286 ms 21016 KB Output is correct
20 Correct 249 ms 21020 KB Output is correct
21 Incorrect 146 ms 20724 KB Output isn't correct
22 Halted 0 ms 0 KB -