oj.uz

Submission #502298

# Submission time Handle Problem Language Result Execution time Memory
502298 2022-01-05T17:54:22 Z cig32 Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 521276 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 2e5 + 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;
    };

    vector<node> a;
    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;
    }
    int sz;
    public:
    void set_mod(long long x) {
        mod = x;
    }
    void update(int l, int r, long long v) {
        u(l, r, 0, sz, 0, v);
    }
    long long query(int l, int r) {
        return qu(l, r, 0, sz, 0);
    }
    void resize(int k) {
        sz = k;
        a.resize(4*k + 10);
    }
};
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].resize(lis[i][j].size());
                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:157:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |                 for(int l=0; l<lis[i][j].size(); l++) {
      |                              ~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 2484 KB Output is correct
2 Correct 1929 ms 2728 KB Output is correct
3 Correct 2305 ms 2632 KB Output is correct
4 Correct 1518 ms 2616 KB Output is correct
5 Correct 1422 ms 2748 KB Output is correct
6 Correct 1465 ms 2620 KB Output is correct
7 Correct 1396 ms 2564 KB Output is correct
8 Correct 1649 ms 2684 KB Output is correct
9 Correct 1671 ms 2796 KB Output is correct
10 Correct 1628 ms 2780 KB Output is correct
11 Correct 1600 ms 2712 KB Output is correct
12 Correct 1619 ms 2704 KB Output is correct
13 Correct 1718 ms 2592 KB Output is correct
14 Correct 1751 ms 2712 KB Output is correct
15 Correct 1637 ms 2696 KB Output is correct
16 Correct 1754 ms 2620 KB Output is correct
17 Correct 1626 ms 2684 KB Output is correct
18 Correct 1087 ms 2704 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 2484 KB Output is correct
2 Correct 1929 ms 2728 KB Output is correct
3 Correct 2305 ms 2632 KB Output is correct
4 Correct 1518 ms 2616 KB Output is correct
5 Correct 1422 ms 2748 KB Output is correct
6 Correct 1465 ms 2620 KB Output is correct
7 Correct 1396 ms 2564 KB Output is correct
8 Correct 1649 ms 2684 KB Output is correct
9 Correct 1671 ms 2796 KB Output is correct
10 Correct 1628 ms 2780 KB Output is correct
11 Correct 1600 ms 2712 KB Output is correct
12 Correct 1619 ms 2704 KB Output is correct
13 Correct 1718 ms 2592 KB Output is correct
14 Correct 1751 ms 2712 KB Output is correct
15 Correct 1637 ms 2696 KB Output is correct
16 Correct 1754 ms 2620 KB Output is correct
17 Correct 1626 ms 2684 KB Output is correct
18 Correct 1087 ms 2704 KB Output is correct
19 Execution timed out 7120 ms 521276 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 2484 KB Output is correct
2 Correct 1929 ms 2728 KB Output is correct
3 Correct 2305 ms 2632 KB Output is correct
4 Correct 1518 ms 2616 KB Output is correct
5 Correct 1422 ms 2748 KB Output is correct
6 Correct 1465 ms 2620 KB Output is correct
7 Correct 1396 ms 2564 KB Output is correct
8 Correct 1649 ms 2684 KB Output is correct
9 Correct 1671 ms 2796 KB Output is correct
10 Correct 1628 ms 2780 KB Output is correct
11 Correct 1600 ms 2712 KB Output is correct
12 Correct 1619 ms 2704 KB Output is correct
13 Correct 1718 ms 2592 KB Output is correct
14 Correct 1751 ms 2712 KB Output is correct
15 Correct 1637 ms 2696 KB Output is correct
16 Correct 1754 ms 2620 KB Output is correct
17 Correct 1626 ms 2684 KB Output is correct
18 Correct 1087 ms 2704 KB Output is correct
19 Correct 2365 ms 2536 KB Output is correct
20 Correct 2622 ms 2596 KB Output is correct
21 Correct 1946 ms 2744 KB Output is correct
22 Correct 1474 ms 2548 KB Output is correct
23 Correct 1805 ms 2688 KB Output is correct
24 Correct 1756 ms 2584 KB Output is correct
25 Correct 2113 ms 2596 KB Output is correct
26 Correct 1706 ms 2488 KB Output is correct
27 Correct 2037 ms 2712 KB Output is correct
28 Correct 1660 ms 2484 KB Output is correct
29 Correct 1952 ms 2820 KB Output is correct
30 Correct 1461 ms 1472 KB Output is correct
31 Correct 1965 ms 1116 KB Output is correct
32 Correct 1991 ms 1244 KB Output is correct
33 Correct 1971 ms 1252 KB Output is correct
34 Correct 1507 ms 1032 KB Output is correct
35 Correct 1913 ms 1208 KB Output is correct
36 Correct 1887 ms 1168 KB Output is correct
37 Correct 1867 ms 1184 KB Output is correct
38 Correct 1864 ms 1264 KB Output is correct
39 Correct 1900 ms 1280 KB Output is correct
40 Correct 1895 ms 1112 KB Output is correct
41 Correct 1844 ms 1140 KB Output is correct
42 Correct 1866 ms 1264 KB Output is correct
43 Correct 1638 ms 1220 KB Output is correct
44 Correct 1874 ms 1216 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 2484 KB Output is correct
2 Correct 1929 ms 2728 KB Output is correct
3 Correct 2305 ms 2632 KB Output is correct
4 Correct 1518 ms 2616 KB Output is correct
5 Correct 1422 ms 2748 KB Output is correct
6 Correct 1465 ms 2620 KB Output is correct
7 Correct 1396 ms 2564 KB Output is correct
8 Correct 1649 ms 2684 KB Output is correct
9 Correct 1671 ms 2796 KB Output is correct
10 Correct 1628 ms 2780 KB Output is correct
11 Correct 1600 ms 2712 KB Output is correct
12 Correct 1619 ms 2704 KB Output is correct
13 Correct 1718 ms 2592 KB Output is correct
14 Correct 1751 ms 2712 KB Output is correct
15 Correct 1637 ms 2696 KB Output is correct
16 Correct 1754 ms 2620 KB Output is correct
17 Correct 1626 ms 2684 KB Output is correct
18 Correct 1087 ms 2704 KB Output is correct
19 Execution timed out 7120 ms 521276 KB Time limit exceeded
20 Halted 0 ms 0 KB -