Submission #750994

#	Time	Username	Problem	Language	Result	Execution time	Memory
750994		joelgun14	Crossing (JOI21_crossing)	C++17	0 / 100	253 ms	1220 KiB

Main

// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
string operate(string a, string b) {
    for(int it = 0; it < a.size(); ++it) {
        if(a[it] == b[it])
            continue;
        bool j = 0, o = 0, i = 0;
        if(a[it] == 'J')
            j = 1;
        else if(a[it] == 'O')
            o = 1;
        else
            i = 1;
        if(b[it] == 'J')
            j = 1;
        else if(b[it] == 'O')
            o = 1;
        else
            i = 1;
        if(!j)
            a[it] = 'J';
        else if(!o)
            a[it] = 'O';
        else
            a[it] = 'I';
    }
    return a;
}
int to_num(string s) {
    if(s == "J")
        return 0;
    else if(s == "O")
        return 1;
    else
        return 2;
}
int to_num(char x) {
    if(x == 'J')
        return 0;
    else if(x == 'O')
        return 1;
    else
        return 2;
}
const int lim = 2e5 + 5;
struct fenwick {
    int a[lim];
    fenwick() {
        memset(a, 0, sizeof(a));
    }
    void update(int idx, int val) {
        while(idx < lim) {
            a[idx] += val;
            idx += (idx&-idx);
        }
    }
    int query(int idx) {
        int res = 0;
        while(idx > 0) {
            res += a[idx];
            idx -= (idx&-idx);
        }
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};
// buat bit 27 state 1 nya implicit disimpan di segment bawahnya
// remove segment bawahnya per segment gtu
// nanti cnt cari mutually exclusive segment
// char akhirnya berapa
// char 1, 2, 3, dan akhir
// 4 pertama -> quadruplet 1
// 4 kedua -> quadruplet 2
bool compatible[3][3][3][3][3][3][3][3];
bool possible[3][3][3][3];
int pref[lim][3][3][3];
int cnt[3][3][3][3];
vector<vector<int>> masks[3][3][3][3];
// precompute itu incompatible pairsnya gmn aja
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int n;
    cin >> n;
    // coba cek tiap possibility pengambilan
    // max pengambilan cmn 3?
    int e[n + 1][3];
    for(int i = 0; i < 3; ++i) {
        for(int j = 1; j <= n; ++j) {
            char x;
            cin >> x;
            e[j][i] = to_num(x);
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                for(int l = 0; l < 3; ++l) {
                    pref[i][j][k][l] += pref[i - 1][j][k][l];
                }
            }
        }
        pref[i][e[i][0]][e[i][1]][e[i][2]]++;
    }
    int q;
    cin >> q;
    set<pair<pair<int, int>, int>> segments;
    for(int i = 1; i <= n; ++i) {
        char x;
        cin >> x;
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                for(int l = 0; l < 3; ++l) {
                    cnt[j][k][l][to_num(x)] += pref[i][j][k][l] - pref[i - 1][j][k][l];
                }
            }
        }
        segments.insert(make_pair(make_pair(i, i), to_num(x)));
    }
    string choice[3] = {"J", "O", "I"};
    vector<vector<int>> triplets;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                triplets.push_back({i, j, k});
            }
        }
    }
    // utk tiap triple consider tiap pengambilan dengan triple itu sendiri, apa bisa buat char tertentu?
    for(auto p : triplets) {
        for(int i = 0; i < 3; ++i) {
            string tmp = choice[p[i]];
            for(int j = 0; j < 3; ++j) {
                tmp = operate(tmp, choice[p[j]]);
                for(int k = 0; k < 3; ++k) {
                    tmp = operate(tmp, choice[p[k]]);
                    possible[p[0]][p[1]][p[2]][to_num(tmp)] = 1;
                    masks[p[0]][p[1]][p[2]][to_num(tmp)].push_back({i, j, k});
                }
            }
        }
    }
    for(int trip = 0; trip < triplets.size(); ++trip) {
        for(int trip2 = 0; trip2 < triplets.size(); ++trip2) {
            vector<int> p1 = triplets[trip], p2 = triplets[trip2];
            for(int i = 0; i < 3; ++i) {
                string tmp1 = choice[p1[i]];
                string tmp2 = choice[p2[i]];
                for(int j = 0; j < 3; ++j) {
                    tmp1 = operate(tmp1, choice[p1[j]]);
                    tmp2 = operate(tmp2, choice[p2[j]]);
                    for(int k = 0; k < 3; ++k) {
                        tmp1 = operate(tmp1, choice[p1[k]]);
                        tmp2 = operate(tmp2, choice[p2[k]]);
                        compatible[p1[0]][p1[1]][p1[2]][to_num(tmp1)][p2[0]][p2[1]][p2[2]][to_num(tmp2)] = 1;
                    }
                }
            }
        }
    }
    // coba permutasi size 1, 2, 3
    // given same sequence tp resultnya beda -> pasti gabisa -> O(81Q) -> 1.6e7
    // klo misal ga ada yg beda, berarti max ada 27 aja
    // klo 27, nanti cek O(27^2*Q) -> 1.4e8
    // total O(81Q)
    bool ans = 1;
    vector<vector<int>> a;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                for(int l = 0; l < 3; ++l) {
                    if(cnt[i][j][k][l] && !possible[i][j][k][l])
                        ans = 0;
                    if(cnt[i][j][k][l])
                        a.push_back({i, j, k, l});
                }
            }
        }
    }
    for(int i = 0; i < a.size(); ++i) {
        for(int j = i + 1; j < a.size(); ++j) {
            if(!compatible[a[i][0]][a[i][1]][a[i][2]][a[i][3]][a[j][0]][a[j][1]][a[j][2]][a[j][3]])
                ans = 0;
        }
    }
    if(ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    while(q--) {
        // jalankan kode update
        int l, r; char x;
        cin >> l >> r >> x;
        while(segments.lower_bound(mp(make_pair(l, 0), 0)) != segments.end() && (*segments.lower_bound(mp(make_pair(l, 0), 0))).fi.se <= r) {
            pair<pair<int, int>, int> tmp = *segments.lower_bound(mp(mp(l, 0), 0));
            int cl = tmp.fi.se, cr = tmp.fi.fi, type = tmp.se;
            segments.erase(tmp);
            if(cl < l) {
                segments.ins(mp(mp(l - 1, cl), type));
            }
            if(cr > r) {
                segments.ins(mp(mp(cr, r + 1), type));
            }
            cl = max(l, cl);
            cr = min(r, cr);
            for(int i = 0; i < 3; ++i) {
                for(int j = 0; j < 3; ++j) {
                    for(int k = 0; k < 3; ++k) {
                        cnt[i][j][k][type] -= pref[cr][i][j][k] - pref[cl - 1][i][j][k];
                        cnt[i][j][k][to_num(x)] += pref[cr][i][j][k] - pref[cl - 1][i][j][k];
                        // cek mask yg bs buat i, j, k jadi type?
                    }
                }
            }
        }
        segments.ins(mp(mp(r, l), to_num(x)));
        // kode cek answer
        bool ans = 1;
        vector<vector<int>> a;
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                for(int k = 0; k < 3; ++k) {
                    for(int l = 0; l < 3; ++l) {
                        if(cnt[i][j][k][l] && !possible[i][j][k][l])
                            ans = 0;
                        if(cnt[i][j][k][l])
                            a.push_back({i, j, k, l});
                    }
                }
            }
        }
        if(!ans) {
            cout << "No" << endl;
            continue;
        }
        // cari subset yg compatiblenya terbanyak?
        int res[3][3][3];
        memset(res, 0, sizeof(res));
        for(int i = 0; i < a.size(); ++i) {
            for(auto j : masks[a[i][0]][a[i][1]][a[i][2]][a[i][3]]) {
                ++res[j[0]][j[1]][j[2]];
            }
        }
        int mx = 0;
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                for(int k = 0; k < 3; ++k)
                    mx = max(mx, res[i][j][k]);
            }
        }
        if(ans && mx == n)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::string operate(std::string, std::string)':
Main.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int it = 0; it < a.size(); ++it) {
      |                     ~~~^~~~~~~~~~
Main.cpp:27:28: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   27 |         bool j = 0, o = 0, i = 0;
      |                            ^
Main.cpp: In function 'int main()':
Main.cpp:164:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int trip = 0; trip < triplets.size(); ++trip) {
      |                       ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:165:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int trip2 = 0; trip2 < triplets.size(); ++trip2) {
      |                            ~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:201:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for(int i = 0; i < a.size(); ++i) {
      |                    ~~^~~~~~~~~~
Main.cpp:202:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         for(int j = i + 1; j < a.size(); ++j) {
      |                            ~~^~~~~~~~~~
Main.cpp:260:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |         for(int i = 0; i < a.size(); ++i) {
      |                        ~~^~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51