oj.uz

Submission #502427

# Submission time Handle Problem Language Result Execution time Memory
502427 2022-01-06T00:58:12 Z cig32 Crossing (JOI21_crossing) C++17
26 / 100
 2050 ms 272268 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

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;
}
int bm(int b, int p) { // bigmod
    if(p==0) return 1;
    int 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 {
        int upd = 0;
        int ans = 0;
        bool exist = 0;
    };

    vector<node> a;
    int mod = 0;
    //To be remained unchanged
    void u(int l, int r, int constl, int constr, int idx, int 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;
    }
    int 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;
        int 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(int x) {
        mod = x;
    }
    void update(int l, int r, int v) {
        u(l, r, 0, sz, 0, v);
    }
    int query(int l, int r) {
        return qu(l, r, 0, sz, 0);
    }
    void resize(int k) {
        sz = k;
        a.resize(4*k + 10);
    }
};
int code(char c) {
    return (c == 'O' ? 1 : (c == 'I' ? 2 : 0));
}
void solve(int tc) {
    int N;
    cin >> N;
    string s[9];
    string word = "JOI";
    for(int i=0; i<3; i++) {
        cin >> s[i];
        for(int j=0; j<N; j++) s[i] += word[rnd(0, 2)];
    }
    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];
    int dist[9] = {};
    int Q = 200000;
    cin >> Q;
    string t0;
    for(int j=0; j<N; j++) t0 += word[rnd(0, 2)];
    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());
                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;
            l = rnd(1, N), r = rnd(1, N);
            if(l > r) swap(l, r);
            cin >> l >> r;
            char c;
            c = word[rnd(0, 2)];
            cin >> c;
            int L[1][3], R[1][3];
            for(int j=0; j<1; 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<1; 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<1; 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:161:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |                 for(int l=0; l<lis[i][j].size(); l++) {
      |                              ~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 868 KB Output is correct
2 Correct 340 ms 972 KB Output is correct
3 Correct 278 ms 1004 KB Output is correct
4 Correct 243 ms 1016 KB Output is correct
5 Correct 218 ms 964 KB Output is correct
6 Correct 216 ms 996 KB Output is correct
7 Correct 243 ms 948 KB Output is correct
8 Correct 235 ms 1168 KB Output is correct
9 Correct 247 ms 964 KB Output is correct
10 Correct 239 ms 1028 KB Output is correct
11 Correct 267 ms 1040 KB Output is correct
12 Correct 259 ms 1044 KB Output is correct
13 Correct 249 ms 964 KB Output is correct
14 Correct 259 ms 996 KB Output is correct
15 Correct 235 ms 924 KB Output is correct
16 Correct 250 ms 1020 KB Output is correct
17 Correct 251 ms 964 KB Output is correct
18 Correct 160 ms 1036 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 868 KB Output is correct
2 Correct 340 ms 972 KB Output is correct
3 Correct 278 ms 1004 KB Output is correct
4 Correct 243 ms 1016 KB Output is correct
5 Correct 218 ms 964 KB Output is correct
6 Correct 216 ms 996 KB Output is correct
7 Correct 243 ms 948 KB Output is correct
8 Correct 235 ms 1168 KB Output is correct
9 Correct 247 ms 964 KB Output is correct
10 Correct 239 ms 1028 KB Output is correct
11 Correct 267 ms 1040 KB Output is correct
12 Correct 259 ms 1044 KB Output is correct
13 Correct 249 ms 964 KB Output is correct
14 Correct 259 ms 996 KB Output is correct
15 Correct 235 ms 924 KB Output is correct
16 Correct 250 ms 1020 KB Output is correct
17 Correct 251 ms 964 KB Output is correct
18 Correct 160 ms 1036 KB Output is correct
19 Correct 2050 ms 270540 KB Output is correct
20 Correct 1906 ms 269848 KB Output is correct
21 Correct 1212 ms 253924 KB Output is correct
22 Correct 1131 ms 228368 KB Output is correct
23 Correct 541 ms 17144 KB Output is correct
24 Correct 547 ms 17064 KB Output is correct
25 Correct 1229 ms 272012 KB Output is correct
26 Correct 1312 ms 272172 KB Output is correct
27 Correct 1341 ms 270436 KB Output is correct
28 Correct 1337 ms 272060 KB Output is correct
29 Correct 1252 ms 262524 KB Output is correct
30 Correct 581 ms 17152 KB Output is correct
31 Correct 1285 ms 270308 KB Output is correct
32 Correct 1229 ms 246272 KB Output is correct
33 Correct 537 ms 16800 KB Output is correct
34 Correct 1391 ms 270320 KB Output is correct
35 Correct 1084 ms 201996 KB Output is correct
36 Correct 557 ms 16948 KB Output is correct
37 Correct 560 ms 16968 KB Output is correct
38 Correct 942 ms 270040 KB Output is correct
39 Correct 844 ms 272268 KB Output is correct
40 Correct 871 ms 178216 KB Output is correct
41 Correct 1124 ms 270436 KB Output is correct
42 Correct 685 ms 269716 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 868 KB Output is correct
2 Correct 340 ms 972 KB Output is correct
3 Correct 278 ms 1004 KB Output is correct
4 Correct 243 ms 1016 KB Output is correct
5 Correct 218 ms 964 KB Output is correct
6 Correct 216 ms 996 KB Output is correct
7 Correct 243 ms 948 KB Output is correct
8 Correct 235 ms 1168 KB Output is correct
9 Correct 247 ms 964 KB Output is correct
10 Correct 239 ms 1028 KB Output is correct
11 Correct 267 ms 1040 KB Output is correct
12 Correct 259 ms 1044 KB Output is correct
13 Correct 249 ms 964 KB Output is correct
14 Correct 259 ms 996 KB Output is correct
15 Correct 235 ms 924 KB Output is correct
16 Correct 250 ms 1020 KB Output is correct
17 Correct 251 ms 964 KB Output is correct
18 Correct 160 ms 1036 KB Output is correct
19 Correct 282 ms 1128 KB Output is correct
20 Correct 287 ms 1092 KB Output is correct
21 Incorrect 235 ms 1168 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 868 KB Output is correct
2 Correct 340 ms 972 KB Output is correct
3 Correct 278 ms 1004 KB Output is correct
4 Correct 243 ms 1016 KB Output is correct
5 Correct 218 ms 964 KB Output is correct
6 Correct 216 ms 996 KB Output is correct
7 Correct 243 ms 948 KB Output is correct
8 Correct 235 ms 1168 KB Output is correct
9 Correct 247 ms 964 KB Output is correct
10 Correct 239 ms 1028 KB Output is correct
11 Correct 267 ms 1040 KB Output is correct
12 Correct 259 ms 1044 KB Output is correct
13 Correct 249 ms 964 KB Output is correct
14 Correct 259 ms 996 KB Output is correct
15 Correct 235 ms 924 KB Output is correct
16 Correct 250 ms 1020 KB Output is correct
17 Correct 251 ms 964 KB Output is correct
18 Correct 160 ms 1036 KB Output is correct
19 Correct 2050 ms 270540 KB Output is correct
20 Correct 1906 ms 269848 KB Output is correct
21 Correct 1212 ms 253924 KB Output is correct
22 Correct 1131 ms 228368 KB Output is correct
23 Correct 541 ms 17144 KB Output is correct
24 Correct 547 ms 17064 KB Output is correct
25 Correct 1229 ms 272012 KB Output is correct
26 Correct 1312 ms 272172 KB Output is correct
27 Correct 1341 ms 270436 KB Output is correct
28 Correct 1337 ms 272060 KB Output is correct
29 Correct 1252 ms 262524 KB Output is correct
30 Correct 581 ms 17152 KB Output is correct
31 Correct 1285 ms 270308 KB Output is correct
32 Correct 1229 ms 246272 KB Output is correct
33 Correct 537 ms 16800 KB Output is correct
34 Correct 1391 ms 270320 KB Output is correct
35 Correct 1084 ms 201996 KB Output is correct
36 Correct 557 ms 16948 KB Output is correct
37 Correct 560 ms 16968 KB Output is correct
38 Correct 942 ms 270040 KB Output is correct
39 Correct 844 ms 272268 KB Output is correct
40 Correct 871 ms 178216 KB Output is correct
41 Correct 1124 ms 270436 KB Output is correct
42 Correct 685 ms 269716 KB Output is correct
43 Correct 282 ms 1128 KB Output is correct
44 Correct 287 ms 1092 KB Output is correct
45 Incorrect 235 ms 1168 KB Output isn't correct
46 Halted 0 ms 0 KB -