oj.uz

Submission #502296

# Submission time Handle Problem Language Result Execution time Memory
502296 2022-01-05T17:50:54 Z cig32 Crossing (JOI21_crossing) C++17
26 / 100
 3437 ms 27780 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 2e2 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
long long bm(long long b, long long p) { // bigmod
    if(p==0) return 1;
    long long r = bm(b, p/2);
    if(p&1) return (((r*r) % MOD) * b) % MOD;
    return (r*r) % MOD;
}
string gene(string a, string b) {
    string c;
    for(int i=0; i<a.size(); i++) {
        if(a[i] == b[i]) c += a[i];
        else {
            string t = "JOI";
            for(int j=0; j<3; j++) {
                if(a[i] != t[j] && b[i] != t[j]) c += t[j];
            }
        }
    }
    return c;
}
struct segtree_rurq { 
    // Range update range query, standard form 4 (assignment/sum)
    struct node {
        long long upd = 0;
        long long ans = 0;
        bool exist = 0;
    } a[4*MAXN];
    long long mod = 0;
    //To be remained unchanged
    void u(int l, int r, int constl, int constr, int idx, long long val) {
        if(l <= constl && constr <= r) {
            a[idx].upd = val;
            a[idx].ans = val * (constr-constl+1);
            a[idx].exist = 1;
            if(mod) {
                a[idx].upd %= mod;
                a[idx].ans %= mod;
            }
            return;
        }
        int mid = (constl+constr) >> 1;
        //Lazy propagation
        if(a[idx].exist == 1) {
            a[2*idx+1].upd = a[idx].upd;
            a[2*idx+2].upd = a[idx].upd;
            a[idx].upd = 0;
            a[2*idx+1].exist = 1;
            a[2*idx+2].exist = 1;
            a[idx].exist = 0;
            a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
            a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
            a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
        }
        
        if(mid<l || r<constl) u(l, r, mid+1, constr, 2*idx+2, val);
        else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
        else {
            u(l, r, constl, mid, 2*idx+1, val);
            u(l, r, mid+1, constr, 2*idx+2, val);
        }
        a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
        if(mod) a[idx].ans %= mod;
    }
    long long qu(int l, int r, int constl, int constr, int idx) {
        if(l <= constl && constr <= r) return a[idx].ans;
        int mid = (constl+constr) >> 1;
        long long ret;
        if(a[idx].exist == 1) {
            a[2*idx+1].upd = a[idx].upd;
            a[2*idx+2].upd = a[idx].upd;
            a[idx].upd = 0;
            a[2*idx+1].exist = 1;
            a[2*idx+2].exist = 1;
            a[idx].exist = 0;
            a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
            a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
            a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
        }
        if(mid<l || r<constl) { 
            ret = qu(l, r, mid+1, constr, 2*idx+2);
        }
        else if(constr<l || r<mid+1) {
            ret = qu(l, r, constl, mid, 2*idx+1);
        }
        else {
            ret = qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
        }
        if(mod) ret %= mod;
        return ret;
    }
    public:
    void set_mod(long long x) {
        mod = x;
    }
    void update(int l, int r, long long v) {
        u(l, r, 0, MAXN-1, 0, v);
    }
    long long query(int l, int r) {
        return qu(l, r, 0, MAXN-1, 0);
    }
};
void solve(int tc) {
    int N;
    cin >> N;
    string s[9];
    for(int i=0; i<3; i++) cin >> s[i];
    s[3] = gene(s[0], s[1]);
    s[4] = gene(s[0], s[2]);
    s[5] = gene(s[1], s[2]);
    s[6] = gene(s[2], s[3]);
    s[7] = gene(s[1], s[4]);
    s[8] = gene(s[0], s[5]);
    segtree_rurq st[9][3][3];
    string word = "JOI";
    unordered_map<char, int> code;
    code['J']=0, code['O']=1, code['I']=2;
    int dist[9] = {};
    int Q;
    cin >> Q;
    string t0;
    cin >> t0;
    for(int i=0; i<9; i++) {
        for(int j=0; j<N; j++) {
            if(t0[j] != s[i][j]) dist[i]++;
        }
    }
    vector<int> lis[9][3];
    for(int i=0; i<9; i++) {
        for(int j=0; j<N; j++) {
            lis[i][code[s[i][j]]].push_back(j+1);
        }
    }
    
    for(int i=0; i<9; i++) {
        for(int j=0; j<3; j++) {
            for(int k=0; k<3; k++) {
                if(lis[i][j].empty()) continue;
                st[i][j][k].update(0, lis[i][j].size(), 0);
                for(int l=0; l<lis[i][j].size(); l++) { 
                    if(t0[lis[i][j][l] - 1] == word[k]) {
                        st[i][j][k].update(l+1, l+1, 1);
                    }
                }
            }
        }
    }
    
    for(int i=0; i<=Q; i++) {
        if(i > 0) {
            int l, r;
            cin >> l >> r;
            char c;
            cin >> c;
            int L[9][3], R[9][3];
            for(int j=0; j<9; j++) {
                for(int k=0; k<3; k++) {
                    if(lis[j][k].empty()) {
                        L[j][k] = R[j][k] = -1;
                        continue;
                    }
                    int lb = 0, rb = lis[j][k].size() - 1;
                    while(lb < rb) {
                        int mid = (lb+rb) >> 1;
                        if(lis[j][k][mid] >= l) rb = mid;
                        else lb = mid+1;
                    }
                    L[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
                    lb = 0, rb = lis[j][k].size() - 1;
                    while(lb < rb) {
                        int mid = (lb+rb+1) >> 1;
                        if(lis[j][k][mid] <= r) lb = mid;
                        else rb = mid-1;
                    }
                    R[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
                }
            }
            for(int j=0; j<9; j++) {
                for(int k=0; k<3; k++) {
                    if(L[j][k] == -1 || R[j][k] == -1) continue;
                    for(int m=0; m<3; m++) {
                        st[j][k][m].update(L[j][k], R[j][k], 0);
                    }
                    st[j][k][code[c]].update(L[j][k], R[j][k], 1);
                }
                dist[j] = 0;
                for(int k=0; k<3; k++) {
                    if(lis[j][k].empty()) continue;
                    for(int m=0; m<3; m++) {
                        if(k != m) dist[j] += st[j][k][m].query(1, lis[j][k].size());
                    }
                }
            }
        }
        bool ret = 0;
        for(int j=0; j<9; j++) {
            ret |= (dist[j] == 0);
        }
        cout << (ret ? "Yes\n" : "No\n");
    }
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

Compilation message

Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<a.size(); i++) {
      |                  ~^~~~~~~~~
Main.cpp: In function 'void solve(int)':
Main.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 for(int l=0; l<lis[i][j].size(); l++) {
      |                              ~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 3128 KB Output is correct
2 Correct 2612 ms 3180 KB Output is correct
3 Correct 3187 ms 3224 KB Output is correct
4 Correct 1967 ms 3236 KB Output is correct
5 Correct 2025 ms 3192 KB Output is correct
6 Correct 1905 ms 3200 KB Output is correct
7 Correct 1815 ms 3176 KB Output is correct
8 Correct 2051 ms 3196 KB Output is correct
9 Correct 2147 ms 3140 KB Output is correct
10 Correct 2193 ms 3168 KB Output is correct
11 Correct 2021 ms 3312 KB Output is correct
12 Correct 2145 ms 3252 KB Output is correct
13 Correct 2118 ms 3140 KB Output is correct
14 Correct 2029 ms 3280 KB Output is correct
15 Correct 2146 ms 3240 KB Output is correct
16 Correct 2130 ms 3196 KB Output is correct
17 Correct 2133 ms 3160 KB Output is correct
18 Correct 1347 ms 3296 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 3128 KB Output is correct
2 Correct 2612 ms 3180 KB Output is correct
3 Correct 3187 ms 3224 KB Output is correct
4 Correct 1967 ms 3236 KB Output is correct
5 Correct 2025 ms 3192 KB Output is correct
6 Correct 1905 ms 3200 KB Output is correct
7 Correct 1815 ms 3176 KB Output is correct
8 Correct 2051 ms 3196 KB Output is correct
9 Correct 2147 ms 3140 KB Output is correct
10 Correct 2193 ms 3168 KB Output is correct
11 Correct 2021 ms 3312 KB Output is correct
12 Correct 2145 ms 3252 KB Output is correct
13 Correct 2118 ms 3140 KB Output is correct
14 Correct 2029 ms 3280 KB Output is correct
15 Correct 2146 ms 3240 KB Output is correct
16 Correct 2130 ms 3196 KB Output is correct
17 Correct 2133 ms 3160 KB Output is correct
18 Correct 1347 ms 3296 KB Output is correct
19 Runtime error 60 ms 27780 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 3128 KB Output is correct
2 Correct 2612 ms 3180 KB Output is correct
3 Correct 3187 ms 3224 KB Output is correct
4 Correct 1967 ms 3236 KB Output is correct
5 Correct 2025 ms 3192 KB Output is correct
6 Correct 1905 ms 3200 KB Output is correct
7 Correct 1815 ms 3176 KB Output is correct
8 Correct 2051 ms 3196 KB Output is correct
9 Correct 2147 ms 3140 KB Output is correct
10 Correct 2193 ms 3168 KB Output is correct
11 Correct 2021 ms 3312 KB Output is correct
12 Correct 2145 ms 3252 KB Output is correct
13 Correct 2118 ms 3140 KB Output is correct
14 Correct 2029 ms 3280 KB Output is correct
15 Correct 2146 ms 3240 KB Output is correct
16 Correct 2130 ms 3196 KB Output is correct
17 Correct 2133 ms 3160 KB Output is correct
18 Correct 1347 ms 3296 KB Output is correct
19 Correct 2891 ms 3216 KB Output is correct
20 Correct 3437 ms 3284 KB Output is correct
21 Correct 2327 ms 3164 KB Output is correct
22 Correct 2004 ms 3172 KB Output is correct
23 Correct 2446 ms 3208 KB Output is correct
24 Correct 2223 ms 3124 KB Output is correct
25 Correct 2465 ms 3432 KB Output is correct
26 Correct 2078 ms 3168 KB Output is correct
27 Correct 2405 ms 3204 KB Output is correct
28 Correct 2155 ms 3388 KB Output is correct
29 Correct 2465 ms 3240 KB Output is correct
30 Correct 2021 ms 3384 KB Output is correct
31 Correct 2603 ms 3912 KB Output is correct
32 Correct 2412 ms 4084 KB Output is correct
33 Correct 2449 ms 3972 KB Output is correct
34 Correct 2145 ms 3976 KB Output is correct
35 Correct 2428 ms 4016 KB Output is correct
36 Correct 2434 ms 3972 KB Output is correct
37 Correct 2435 ms 3968 KB Output is correct
38 Correct 2401 ms 4016 KB Output is correct
39 Correct 2455 ms 3980 KB Output is correct
40 Correct 2411 ms 4140 KB Output is correct
41 Correct 2483 ms 4192 KB Output is correct
42 Correct 2458 ms 4016 KB Output is correct
43 Correct 2286 ms 4088 KB Output is correct
44 Correct 2426 ms 4100 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 3128 KB Output is correct
2 Correct 2612 ms 3180 KB Output is correct
3 Correct 3187 ms 3224 KB Output is correct
4 Correct 1967 ms 3236 KB Output is correct
5 Correct 2025 ms 3192 KB Output is correct
6 Correct 1905 ms 3200 KB Output is correct
7 Correct 1815 ms 3176 KB Output is correct
8 Correct 2051 ms 3196 KB Output is correct
9 Correct 2147 ms 3140 KB Output is correct
10 Correct 2193 ms 3168 KB Output is correct
11 Correct 2021 ms 3312 KB Output is correct
12 Correct 2145 ms 3252 KB Output is correct
13 Correct 2118 ms 3140 KB Output is correct
14 Correct 2029 ms 3280 KB Output is correct
15 Correct 2146 ms 3240 KB Output is correct
16 Correct 2130 ms 3196 KB Output is correct
17 Correct 2133 ms 3160 KB Output is correct
18 Correct 1347 ms 3296 KB Output is correct
19 Runtime error 60 ms 27780 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -