oj.uz

Submission #923007

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

using namespace std;

int n;
int pref[N][2];
const int p = 1998109;
const int q = 1997293;
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 66 ms 5040 KB Output is correct
2 Correct 67 ms 5056 KB Output is correct
3 Correct 69 ms 4948 KB Output is correct
4 Correct 55 ms 4944 KB Output is correct
5 Correct 53 ms 4948 KB Output is correct
6 Correct 55 ms 4944 KB Output is correct
7 Correct 58 ms 5072 KB Output is correct
8 Correct 57 ms 4944 KB Output is correct
9 Correct 60 ms 4948 KB Output is correct
10 Correct 57 ms 5128 KB Output is correct
11 Correct 64 ms 4948 KB Output is correct
12 Correct 57 ms 5132 KB Output is correct
13 Correct 58 ms 4952 KB Output is correct
14 Correct 57 ms 5056 KB Output is correct
15 Correct 58 ms 4948 KB Output is correct
16 Correct 57 ms 5072 KB Output is correct
17 Correct 62 ms 5048 KB Output is correct
18 Correct 72 ms 4948 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5040 KB Output is correct
2 Correct 67 ms 5056 KB Output is correct
3 Correct 69 ms 4948 KB Output is correct
4 Correct 55 ms 4944 KB Output is correct
5 Correct 53 ms 4948 KB Output is correct
6 Correct 55 ms 4944 KB Output is correct
7 Correct 58 ms 5072 KB Output is correct
8 Correct 57 ms 4944 KB Output is correct
9 Correct 60 ms 4948 KB Output is correct
10 Correct 57 ms 5128 KB Output is correct
11 Correct 64 ms 4948 KB Output is correct
12 Correct 57 ms 5132 KB Output is correct
13 Correct 58 ms 4952 KB Output is correct
14 Correct 57 ms 5056 KB Output is correct
15 Correct 58 ms 4948 KB Output is correct
16 Correct 57 ms 5072 KB Output is correct
17 Correct 62 ms 5048 KB Output is correct
18 Correct 72 ms 4948 KB Output is correct
19 Correct 254 ms 23808 KB Output is correct
20 Correct 235 ms 24592 KB Output is correct
21 Incorrect 140 ms 24132 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5040 KB Output is correct
2 Correct 67 ms 5056 KB Output is correct
3 Correct 69 ms 4948 KB Output is correct
4 Correct 55 ms 4944 KB Output is correct
5 Correct 53 ms 4948 KB Output is correct
6 Correct 55 ms 4944 KB Output is correct
7 Correct 58 ms 5072 KB Output is correct
8 Correct 57 ms 4944 KB Output is correct
9 Correct 60 ms 4948 KB Output is correct
10 Correct 57 ms 5128 KB Output is correct
11 Correct 64 ms 4948 KB Output is correct
12 Correct 57 ms 5132 KB Output is correct
13 Correct 58 ms 4952 KB Output is correct
14 Correct 57 ms 5056 KB Output is correct
15 Correct 58 ms 4948 KB Output is correct
16 Correct 57 ms 5072 KB Output is correct
17 Correct 62 ms 5048 KB Output is correct
18 Correct 72 ms 4948 KB Output is correct
19 Correct 65 ms 5076 KB Output is correct
20 Correct 70 ms 5044 KB Output is correct
21 Incorrect 57 ms 4912 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5040 KB Output is correct
2 Correct 67 ms 5056 KB Output is correct
3 Correct 69 ms 4948 KB Output is correct
4 Correct 55 ms 4944 KB Output is correct
5 Correct 53 ms 4948 KB Output is correct
6 Correct 55 ms 4944 KB Output is correct
7 Correct 58 ms 5072 KB Output is correct
8 Correct 57 ms 4944 KB Output is correct
9 Correct 60 ms 4948 KB Output is correct
10 Correct 57 ms 5128 KB Output is correct
11 Correct 64 ms 4948 KB Output is correct
12 Correct 57 ms 5132 KB Output is correct
13 Correct 58 ms 4952 KB Output is correct
14 Correct 57 ms 5056 KB Output is correct
15 Correct 58 ms 4948 KB Output is correct
16 Correct 57 ms 5072 KB Output is correct
17 Correct 62 ms 5048 KB Output is correct
18 Correct 72 ms 4948 KB Output is correct
19 Correct 254 ms 23808 KB Output is correct
20 Correct 235 ms 24592 KB Output is correct
21 Incorrect 140 ms 24132 KB Output isn't correct
22 Halted 0 ms 0 KB -