oj.uz

Submission #923004

# Submission time Handle Problem Language Result Execution time Memory
923004 2024-02-06T12:29:25 Z PagodePaiva Crossing (JOI21_crossing) C++17
3 / 100
 382 ms 4928 KB 
#include<bits/stdc++.h>
#define N 100010

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;

int 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 315 ms 4432 KB Output is correct
2 Correct 333 ms 4596 KB Output is correct
3 Correct 382 ms 4584 KB Output is correct
4 Correct 353 ms 4388 KB Output is correct
5 Correct 338 ms 4436 KB Output is correct
6 Correct 325 ms 4684 KB Output is correct
7 Correct 320 ms 4432 KB Output is correct
8 Correct 332 ms 4432 KB Output is correct
9 Correct 333 ms 4440 KB Output is correct
10 Correct 328 ms 4432 KB Output is correct
11 Correct 323 ms 4480 KB Output is correct
12 Correct 333 ms 4528 KB Output is correct
13 Correct 321 ms 4600 KB Output is correct
14 Correct 329 ms 4928 KB Output is correct
15 Correct 347 ms 4432 KB Output is correct
16 Correct 328 ms 4580 KB Output is correct
17 Correct 320 ms 4732 KB Output is correct
18 Correct 355 ms 4836 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 4432 KB Output is correct
2 Correct 333 ms 4596 KB Output is correct
3 Correct 382 ms 4584 KB Output is correct
4 Correct 353 ms 4388 KB Output is correct
5 Correct 338 ms 4436 KB Output is correct
6 Correct 325 ms 4684 KB Output is correct
7 Correct 320 ms 4432 KB Output is correct
8 Correct 332 ms 4432 KB Output is correct
9 Correct 333 ms 4440 KB Output is correct
10 Correct 328 ms 4432 KB Output is correct
11 Correct 323 ms 4480 KB Output is correct
12 Correct 333 ms 4528 KB Output is correct
13 Correct 321 ms 4600 KB Output is correct
14 Correct 329 ms 4928 KB Output is correct
15 Correct 347 ms 4432 KB Output is correct
16 Correct 328 ms 4580 KB Output is correct
17 Correct 320 ms 4732 KB Output is correct
18 Correct 355 ms 4836 KB Output is correct
19 Runtime error 10 ms 3520 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 315 ms 4432 KB Output is correct
2 Correct 333 ms 4596 KB Output is correct
3 Correct 382 ms 4584 KB Output is correct
4 Correct 353 ms 4388 KB Output is correct
5 Correct 338 ms 4436 KB Output is correct
6 Correct 325 ms 4684 KB Output is correct
7 Correct 320 ms 4432 KB Output is correct
8 Correct 332 ms 4432 KB Output is correct
9 Correct 333 ms 4440 KB Output is correct
10 Correct 328 ms 4432 KB Output is correct
11 Correct 323 ms 4480 KB Output is correct
12 Correct 333 ms 4528 KB Output is correct
13 Correct 321 ms 4600 KB Output is correct
14 Correct 329 ms 4928 KB Output is correct
15 Correct 347 ms 4432 KB Output is correct
16 Correct 328 ms 4580 KB Output is correct
17 Correct 320 ms 4732 KB Output is correct
18 Correct 355 ms 4836 KB Output is correct
19 Correct 315 ms 4436 KB Output is correct
20 Correct 334 ms 4404 KB Output is correct
21 Incorrect 355 ms 4604 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 4432 KB Output is correct
2 Correct 333 ms 4596 KB Output is correct
3 Correct 382 ms 4584 KB Output is correct
4 Correct 353 ms 4388 KB Output is correct
5 Correct 338 ms 4436 KB Output is correct
6 Correct 325 ms 4684 KB Output is correct
7 Correct 320 ms 4432 KB Output is correct
8 Correct 332 ms 4432 KB Output is correct
9 Correct 333 ms 4440 KB Output is correct
10 Correct 328 ms 4432 KB Output is correct
11 Correct 323 ms 4480 KB Output is correct
12 Correct 333 ms 4528 KB Output is correct
13 Correct 321 ms 4600 KB Output is correct
14 Correct 329 ms 4928 KB Output is correct
15 Correct 347 ms 4432 KB Output is correct
16 Correct 328 ms 4580 KB Output is correct
17 Correct 320 ms 4732 KB Output is correct
18 Correct 355 ms 4836 KB Output is correct
19 Runtime error 10 ms 3520 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -