oj.uz

Submission #502423

# Submission time Handle Problem Language Result Execution time Memory
502423 2022-01-06T00:10:35 Z cig32 Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 266544 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int int
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);
    }
};
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 1566 ms 1096 KB Output is correct
2 Correct 1830 ms 1316 KB Output is correct
3 Correct 2144 ms 1244 KB Output is correct
4 Correct 1432 ms 1140 KB Output is correct
5 Correct 1420 ms 1200 KB Output is correct
6 Correct 1530 ms 1116 KB Output is correct
7 Correct 1391 ms 1296 KB Output is correct
8 Correct 1745 ms 1240 KB Output is correct
9 Correct 1683 ms 1192 KB Output is correct
10 Correct 1707 ms 1264 KB Output is correct
11 Correct 1662 ms 1256 KB Output is correct
12 Correct 1574 ms 1240 KB Output is correct
13 Correct 1698 ms 1248 KB Output is correct
14 Correct 1626 ms 1212 KB Output is correct
15 Correct 1573 ms 1212 KB Output is correct
16 Correct 1681 ms 1216 KB Output is correct
17 Correct 1643 ms 1232 KB Output is correct
18 Correct 1024 ms 1276 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 1096 KB Output is correct
2 Correct 1830 ms 1316 KB Output is correct
3 Correct 2144 ms 1244 KB Output is correct
4 Correct 1432 ms 1140 KB Output is correct
5 Correct 1420 ms 1200 KB Output is correct
6 Correct 1530 ms 1116 KB Output is correct
7 Correct 1391 ms 1296 KB Output is correct
8 Correct 1745 ms 1240 KB Output is correct
9 Correct 1683 ms 1192 KB Output is correct
10 Correct 1707 ms 1264 KB Output is correct
11 Correct 1662 ms 1256 KB Output is correct
12 Correct 1574 ms 1240 KB Output is correct
13 Correct 1698 ms 1248 KB Output is correct
14 Correct 1626 ms 1212 KB Output is correct
15 Correct 1573 ms 1212 KB Output is correct
16 Correct 1681 ms 1216 KB Output is correct
17 Correct 1643 ms 1232 KB Output is correct
18 Correct 1024 ms 1276 KB Output is correct
19 Execution timed out 7064 ms 266544 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 1096 KB Output is correct
2 Correct 1830 ms 1316 KB Output is correct
3 Correct 2144 ms 1244 KB Output is correct
4 Correct 1432 ms 1140 KB Output is correct
5 Correct 1420 ms 1200 KB Output is correct
6 Correct 1530 ms 1116 KB Output is correct
7 Correct 1391 ms 1296 KB Output is correct
8 Correct 1745 ms 1240 KB Output is correct
9 Correct 1683 ms 1192 KB Output is correct
10 Correct 1707 ms 1264 KB Output is correct
11 Correct 1662 ms 1256 KB Output is correct
12 Correct 1574 ms 1240 KB Output is correct
13 Correct 1698 ms 1248 KB Output is correct
14 Correct 1626 ms 1212 KB Output is correct
15 Correct 1573 ms 1212 KB Output is correct
16 Correct 1681 ms 1216 KB Output is correct
17 Correct 1643 ms 1232 KB Output is correct
18 Correct 1024 ms 1276 KB Output is correct
19 Correct 2309 ms 1252 KB Output is correct
20 Correct 2489 ms 1324 KB Output is correct
21 Correct 1882 ms 1300 KB Output is correct
22 Correct 1428 ms 1168 KB Output is correct
23 Correct 1814 ms 1428 KB Output is correct
24 Correct 1661 ms 1268 KB Output is correct
25 Correct 1831 ms 1364 KB Output is correct
26 Correct 1519 ms 1216 KB Output is correct
27 Correct 1810 ms 1260 KB Output is correct
28 Correct 1542 ms 1248 KB Output is correct
29 Correct 1968 ms 1312 KB Output is correct
30 Correct 1428 ms 1616 KB Output is correct
31 Correct 1960 ms 1328 KB Output is correct
32 Correct 1979 ms 1316 KB Output is correct
33 Correct 1979 ms 1244 KB Output is correct
34 Correct 1598 ms 1356 KB Output is correct
35 Correct 2070 ms 1360 KB Output is correct
36 Correct 1946 ms 1496 KB Output is correct
37 Correct 1980 ms 1260 KB Output is correct
38 Correct 1984 ms 1404 KB Output is correct
39 Correct 1961 ms 1260 KB Output is correct
40 Correct 1903 ms 1352 KB Output is correct
41 Correct 1904 ms 1308 KB Output is correct
42 Correct 1896 ms 1212 KB Output is correct
43 Correct 1650 ms 1320 KB Output is correct
44 Correct 1908 ms 1388 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 1096 KB Output is correct
2 Correct 1830 ms 1316 KB Output is correct
3 Correct 2144 ms 1244 KB Output is correct
4 Correct 1432 ms 1140 KB Output is correct
5 Correct 1420 ms 1200 KB Output is correct
6 Correct 1530 ms 1116 KB Output is correct
7 Correct 1391 ms 1296 KB Output is correct
8 Correct 1745 ms 1240 KB Output is correct
9 Correct 1683 ms 1192 KB Output is correct
10 Correct 1707 ms 1264 KB Output is correct
11 Correct 1662 ms 1256 KB Output is correct
12 Correct 1574 ms 1240 KB Output is correct
13 Correct 1698 ms 1248 KB Output is correct
14 Correct 1626 ms 1212 KB Output is correct
15 Correct 1573 ms 1212 KB Output is correct
16 Correct 1681 ms 1216 KB Output is correct
17 Correct 1643 ms 1232 KB Output is correct
18 Correct 1024 ms 1276 KB Output is correct
19 Execution timed out 7064 ms 266544 KB Time limit exceeded
20 Halted 0 ms 0 KB -