Submission #1148013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148013		yeediot	Crossing (JOI21_crossing)	C++20	0 / 100	53 ms	19776 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
    freopen("/Users/iantsai/cpp/input.txt","r",stdin);
    freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mod = 1e9 + 1021, mxn = 2e5 + 5;
int pw[mxn][2], pre[mxn][2], P[2];
struct SEG{
    int seg[4 * mxn][2], tag[4 * mxn];
    void build(){
        memset(seg, 0, sizeof(seg));
        for(int i = 0; i < 4 * mxn; i++){
            tag[i] = -1;
        }
    }
    void apply(int l, int r, int id, int v){
        for(int j = 0; j < 2; j++){
            seg[id][j] = pre[r - l][j] * (v + 1) % mod;
        }
        tag[id] = v;
    }
    void push(int l, int r, int id){
        if(tag[id] == -1) return;
        int mm = l + r >> 1;
        apply(l, mm, id * 2, tag[id]);
        apply(mm + 1, r, id * 2 + 1, tag[id]);
        tag[id] = -1;
    }
    void pull(int l, int r, int id){
        int mm = l + r >> 1;
        for(int j = 0; j < 2; j++){
            seg[id][j] = (seg[id * 2 + 1][j] + seg[id * 2][j] * pw[r - mm][j] % mod) % mod;
        }
    }
    void m(int l, int r, int id, int ql, int qr, int v){
        if(qr < l or r < ql){
            return;
        }
        if(ql <= l and r <= qr){
            apply(l, r, id, v);
            return;
        }
        int mm = l + r >> 1;
        push(l, r, id);
        m(l, mm, id * 2, ql, qr, v);
        m(mm + 1, r, id * 2 + 1, ql, qr, v);
        pull(l, r, id);
    }
}tr;
void solve(){
    P[0] = 1e9 + 7, P[1] = 1e9 + 9;
    int n;
    cin >> n;
    vector<vector<int>>s(4, vector<int>(n + 1));
    set<int>ck[2];
    for(int j = 0; j < 2; j++){
        pw[0][j] = 1;
        pre[0][j] = 1;
        for(int i = 1; i <= n; i++){
            pw[i][j] = pw[i - 1][j] * P[j] % mod;
            pre[i][j] = (pre[i - 1][j] + pw[i][j]) % mod;
        }
    }
    for(int i = 1; i <= 3; i++){
        vector<int>h(2);
        for(int j = 1; j <= n; j++){
            char c;
            cin >> c;
            s[i][j] = (c == 'J' ? 0 : c == 'O' ? 1 : 2);
            int v = s[i][j];
            for(int k = 0; k < 2; k++){
                h[k] = (h[k] * P[k] % mod + (v + 1)) % mod;
            }
        }
        for(int k = 0; k < 2; k++){
            ck[k].insert(h[k]);
        }
    }
    for(int i = 0; i <= 3; i++){
        for(int j = 0; j <= 3; j++){
            for(int k = 0; k <= 3; k++){
                vector<int>h(2);
                for(int p = 1; p <= n; p++){
                    int v = (s[i][p] * 2 + s[j][p] * 2) % 3;
                    v = (v * 2 + s[k][p] * 2) % 3;
                    for(int k = 0; k < 2; k++){
                        h[k] = (h[k] * P[k] % mod + (v + 1)) % mod;
                    }
                }
                for(int k = 0; k < 2; k++){
                    ck[k].insert(h[k]);
                }
            }
        }
    }
    int q;
    cin >> q;
    tr.build();
    {
        vector<int>h(2);
        for(int j = 1; j <= n; j++){
            char c;
            cin >> c;
            int v = c == 'J' ? 0 : c == 'O' ? 1 : 2;
            tr.m(1, n, 1, j, j, v);
        }
    }
    auto check = [&](){
        bool ok = 1;
        for(int i = 0; i < 2; i++){
            if(ck[i].find(tr.seg[1][i]) == ck[i].end()){
                ok = 0;
                break;
            }
        }
        return ok;
    };
    cout << (check() ? "Yes\n" : "No\n");
    while(q--){
        int l, r, v;
        char c;
        cin >> l >> r >> c;
        v = c == 'J' ? 0 : c == 'O' ? 1 : 2;
        tr.m(1, n, 1, l, r, v);
        cout << (check() ? "Yes\n" : "No\n");
    }
}
signed main(){
    TOI_is_so_de;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef local
    CHECK();
    #endif
}
/*
input:
 
*/
#ifdef local
void CHECK(){
    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
        std::ifstream file1(p1);
        std::ifstream file2(p2);
        if(!file1.is_open() || !file2.is_open()) return false;
        std::string line1, line2;
        while (getline(file1, line1) && getline(file2, line2)) {
            if (line1 != line2)return false;
        }
        int cnta = 0, cntb = 0;
        while(getline(file1,line1))cnta++;
        while(getline(file2,line2))cntb++;
        return cntb - cnta <= 1;
    };
    bool check = compareFiles("output.txt","expected.txt");
    if(check) cerr<<"ACCEPTED\n";
    else cerr<<"WRONG ANSWER!\n";
}
#else
#endif

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