Submission #423419

#	Time	Username	Problem	Language	Result	Execution time	Memory
423419		qwerasdfzxcl	Crossing (JOI21_crossing)	C++14	100 / 100	2975 ms	78256 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int mp[202];
string y;
string a[9];
struct Seg{
    pair<int, bool> tree[800800];
    int lazy[800800];
    pair<int, bool> combine(pair<int, bool> z, pair<int, bool> w){
        pair<int, bool> ret = {0, 0};
        if (z.first==w.first) ret.first = z.first;
        ret.second = z.second&w.second;
        return ret;
    }
    void init(int i, int l, int r, int idx){
        if (l!=r){
            int m = (l+r)>>1;
            init(i<<1, l, m, idx); init(i<<1|1, m+1, r, idx);
            tree[i] = combine(tree[i<<1], tree[i<<1|1]);
        }
        else{
            tree[i] = {mp[a[idx][l]], 0};
            if (a[idx][l]==y[l]) tree[i].second = 1;
        }
    }
    void propagate(int i, int l, int r){
        if (!lazy[i]) return;
        if (tree[i].first==lazy[i]) tree[i].second = 1;
        else tree[i].second = 0;
        if (l!=r){
            lazy[i<<1] = lazy[i], lazy[i<<1|1] = lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] = val; propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, val);
        update(i<<1|1, m+1, r, s, e, val);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }

}tree[9];

char inv[3];
string f(int a1, int a2, int a3){
    string ret;
    ret.resize(a[0].size());
    for (int i=0;i<(int)a[0].size();i++){
        int val = mp[a[0][i]]*a1+mp[a[1][i]]*a2+mp[a[2][i]]*a3;
        val %= 3;
        ret[i] = inv[val];
    }
    return ret;
}

bool chk(){
    bool ret = 0;
    for (int i=0;i<9;i++) ret |= tree[i].tree[1].second;
    return ret;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    mp['J'] = 1, mp['O'] = 2, mp['I'] = 3;
    inv[0] = 'I', inv[1] = 'J', inv[2] = 'O';
    int n, q;
    cin >> n;
    cin >> a[0] >> a[1] >> a[2];
    a[3] = f(2, 2, 0);
    a[4] = f(0, 2, 2);
    a[5] = f(2, 0, 2);
    a[6] = f(1, 1, 2);
    a[7] = f(1, 2, 1);
    a[8] = f(2, 1, 1);
    cin >> q;
    cin >> y;
    for (int i=0;i<9;i++) tree[i].init(1, 0, n-1, i);
    if (chk()) cout << "Yes\n";
    else cout << "No\n";
    while(q--){
        int l, r;
        char tmp;
        cin >> l >> r >> tmp;
        for (int i=0;i<9;i++) tree[i].update(1, 1, n, l, r, mp[tmp]);
        if (chk()) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Seg::init(int, int, int, int)':
Main.cpp:24:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |             tree[i] = {mp[a[idx][l]], 0};
      |                                    ^
Main.cpp: In function 'std::string f(int, int, int)':
Main.cpp:57:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |         int val = mp[a[0][i]]*a1+mp[a[1][i]]*a2+mp[a[2][i]]*a3;
      |                             ^
Main.cpp:57:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |         int val = mp[a[0][i]]*a1+mp[a[1][i]]*a2+mp[a[2][i]]*a3;
      |                                            ^
Main.cpp:57:59: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |         int val = mp[a[0][i]]*a1+mp[a[1][i]]*a2+mp[a[2][i]]*a3;
      |                                                           ^
Main.cpp: In function 'int main()':
Main.cpp:93:64: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |         for (int i=0;i<9;i++) tree[i].update(1, 1, n, l, r, mp[tmp]);
      |                                                                ^~~

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