oj.uz

Submission #533841

# Submission time Handle Problem Language Result Execution time Memory
533841 2022-03-07T11:56:35 Z someone Crossing (JOI21_crossing) C++14
0 / 100
 167 ms 10172 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int M = 1 << 18, N = 2 * M, MOD = 1e9 + 7;
 
deque<int> mini;
int n, q, ans = 0, val[3][M], hashval[N], len[M], pow3[M+1], cumP[M+1], tag_a[N], tag_b[N];
 
inline void updNode(int i, int a, int b, int d, int f) {
    if(a == 0) {
        tag_a[i] = 0;
        tag_b[i] = b;
        hashval[i] = (b * cumP[f - d]) % MOD;
    }
}
 
int update(int i, int deb, int fin, int a, int b, int d = 0, int f = M) {
    if(deb <= d && f <= fin) {
        updNode(i, a, b, d, f);
        return hashval[i];
    }
    if(f <= deb || fin <= d)
        return 0;
    
    int med = (d + f) >> 1;
    updNode(i*2, tag_a[i], tag_b[i], d, med);
    updNode(i*2+1, tag_a[i], tag_b[i], med, f);
    
    tag_a[i] = 1;
    tag_b[i] = 0;
    
    int val1 = update(i*2, deb, fin, a, b, d, med),
        val2 = update(i*2+1, deb, fin, a, b, med, f);
    
    hashval[i] = (hashval[i*2] * pow3[f-med] + hashval[i*2+1]) % MOD;
  
    if(deb < med && med < fin)
        return (val1 * pow3[fin-med] + val2) % MOD;
    else
        return max(val1, val2);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < N; i++)
        tag_a[i] = 1;
    
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < n; j++) {
            char c; cin >> c;
            if(c == 'O')
                val[i][j] = 1;
            else if(c == 'I')
                val[i][j] = 2;
        }
    }
    
    set<int> pos;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) {
            int hashing = 0;
            for(int k = 0; k < n; k++)
                hashing = (hashing * 3 + (i * (val[0][k] + val[1][k] + val[2][k]) + val[j][k]) % 3) % MOD;
            pos.insert(hashing);
        }
  
    pow3[0] = 1;
    for(int i = 1; i <= M; i++)
        pow3[i] = (pow3[i-1] * 3) % MOD;
    for(int i = 1; i <= M; i++)
        cumP[i] = (pow3[i-1] + cumP[i-1]) % MOD;
    
    cin >> q;
    for(int i = 0; i < n; i++) {
        char c; cin >> c;
        if(c == 'O')
            update(1, i, i+1, 0, 1);
        else if(c == 'I')
            update(1, i, i+1, 0, 2);
    }
    
    if(pos.find(update(1, 0, n, 1, 0)) == pos.end())
        cout << "No\n";
    else
        cout << "Yes\n";
    
    for(int i = 0; i < q; i++) {
        char c;
        int deb, fin;
        cin >> deb >> fin >> c;
        deb--;
        if(c == 'J')
            update(1, deb, fin, 0, 0);
        else if(c == 'O')
            update(1, deb, fin, 0, 1);
        else if(c == 'I')
            update(1, deb, fin, 0, 2);
        if(pos.find(update(1, 0, n, 1, 0)) == pos.end())
            cout << "No\n";
        else
            cout << "Yes\n";
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9296 KB Output is correct
2 Correct 165 ms 10160 KB Output is correct
3 Correct 159 ms 10024 KB Output is correct
4 Correct 156 ms 10104 KB Output is correct
5 Correct 167 ms 10128 KB Output is correct
6 Correct 137 ms 10008 KB Output is correct
7 Correct 159 ms 10052 KB Output is correct
8 Correct 156 ms 10172 KB Output is correct
9 Correct 161 ms 10144 KB Output is correct
10 Incorrect 153 ms 10128 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9296 KB Output is correct
2 Correct 165 ms 10160 KB Output is correct
3 Correct 159 ms 10024 KB Output is correct
4 Correct 156 ms 10104 KB Output is correct
5 Correct 167 ms 10128 KB Output is correct
6 Correct 137 ms 10008 KB Output is correct
7 Correct 159 ms 10052 KB Output is correct
8 Correct 156 ms 10172 KB Output is correct
9 Correct 161 ms 10144 KB Output is correct
10 Incorrect 153 ms 10128 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9296 KB Output is correct
2 Correct 165 ms 10160 KB Output is correct
3 Correct 159 ms 10024 KB Output is correct
4 Correct 156 ms 10104 KB Output is correct
5 Correct 167 ms 10128 KB Output is correct
6 Correct 137 ms 10008 KB Output is correct
7 Correct 159 ms 10052 KB Output is correct
8 Correct 156 ms 10172 KB Output is correct
9 Correct 161 ms 10144 KB Output is correct
10 Incorrect 153 ms 10128 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9296 KB Output is correct
2 Correct 165 ms 10160 KB Output is correct
3 Correct 159 ms 10024 KB Output is correct
4 Correct 156 ms 10104 KB Output is correct
5 Correct 167 ms 10128 KB Output is correct
6 Correct 137 ms 10008 KB Output is correct
7 Correct 159 ms 10052 KB Output is correct
8 Correct 156 ms 10172 KB Output is correct
9 Correct 161 ms 10144 KB Output is correct
10 Incorrect 153 ms 10128 KB Output isn't correct
11 Halted 0 ms 0 KB -