oj.uz

Submission #923006

# Submission time Handle Problem Language Result Execution time Memory
923006 2024-02-06T12:30:51 Z PagodePaiva Crossing (JOI21_crossing) C++17
3 / 100
 374 ms 7912 KB 
#include<bits/stdc++.h>
#define N 100010
#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(){
    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 330 ms 4852 KB Output is correct
2 Correct 342 ms 5100 KB Output is correct
3 Correct 335 ms 4944 KB Output is correct
4 Correct 314 ms 4968 KB Output is correct
5 Correct 350 ms 4896 KB Output is correct
6 Correct 326 ms 5072 KB Output is correct
7 Correct 366 ms 4876 KB Output is correct
8 Correct 330 ms 5084 KB Output is correct
9 Correct 335 ms 5080 KB Output is correct
10 Correct 322 ms 4948 KB Output is correct
11 Correct 321 ms 4948 KB Output is correct
12 Correct 339 ms 4888 KB Output is correct
13 Correct 371 ms 4948 KB Output is correct
14 Correct 337 ms 4944 KB Output is correct
15 Correct 325 ms 5196 KB Output is correct
16 Correct 342 ms 4948 KB Output is correct
17 Correct 331 ms 5176 KB Output is correct
18 Correct 374 ms 4944 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4852 KB Output is correct
2 Correct 342 ms 5100 KB Output is correct
3 Correct 335 ms 4944 KB Output is correct
4 Correct 314 ms 4968 KB Output is correct
5 Correct 350 ms 4896 KB Output is correct
6 Correct 326 ms 5072 KB Output is correct
7 Correct 366 ms 4876 KB Output is correct
8 Correct 330 ms 5084 KB Output is correct
9 Correct 335 ms 5080 KB Output is correct
10 Correct 322 ms 4948 KB Output is correct
11 Correct 321 ms 4948 KB Output is correct
12 Correct 339 ms 4888 KB Output is correct
13 Correct 371 ms 4948 KB Output is correct
14 Correct 337 ms 4944 KB Output is correct
15 Correct 325 ms 5196 KB Output is correct
16 Correct 342 ms 4948 KB Output is correct
17 Correct 331 ms 5176 KB Output is correct
18 Correct 374 ms 4944 KB Output is correct
19 Runtime error 13 ms 7912 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4852 KB Output is correct
2 Correct 342 ms 5100 KB Output is correct
3 Correct 335 ms 4944 KB Output is correct
4 Correct 314 ms 4968 KB Output is correct
5 Correct 350 ms 4896 KB Output is correct
6 Correct 326 ms 5072 KB Output is correct
7 Correct 366 ms 4876 KB Output is correct
8 Correct 330 ms 5084 KB Output is correct
9 Correct 335 ms 5080 KB Output is correct
10 Correct 322 ms 4948 KB Output is correct
11 Correct 321 ms 4948 KB Output is correct
12 Correct 339 ms 4888 KB Output is correct
13 Correct 371 ms 4948 KB Output is correct
14 Correct 337 ms 4944 KB Output is correct
15 Correct 325 ms 5196 KB Output is correct
16 Correct 342 ms 4948 KB Output is correct
17 Correct 331 ms 5176 KB Output is correct
18 Correct 374 ms 4944 KB Output is correct
19 Correct 336 ms 5180 KB Output is correct
20 Correct 344 ms 4948 KB Output is correct
21 Incorrect 328 ms 5132 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4852 KB Output is correct
2 Correct 342 ms 5100 KB Output is correct
3 Correct 335 ms 4944 KB Output is correct
4 Correct 314 ms 4968 KB Output is correct
5 Correct 350 ms 4896 KB Output is correct
6 Correct 326 ms 5072 KB Output is correct
7 Correct 366 ms 4876 KB Output is correct
8 Correct 330 ms 5084 KB Output is correct
9 Correct 335 ms 5080 KB Output is correct
10 Correct 322 ms 4948 KB Output is correct
11 Correct 321 ms 4948 KB Output is correct
12 Correct 339 ms 4888 KB Output is correct
13 Correct 371 ms 4948 KB Output is correct
14 Correct 337 ms 4944 KB Output is correct
15 Correct 325 ms 5196 KB Output is correct
16 Correct 342 ms 4948 KB Output is correct
17 Correct 331 ms 5176 KB Output is correct
18 Correct 374 ms 4944 KB Output is correct
19 Runtime error 13 ms 7912 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -