Submission #906005

#	Time	Username	Problem	Language	Result	Execution time	Memory
906005		hmm789	Crossing (JOI21_crossing)	C++14	100 / 100	5637 ms	307304 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353

struct node {
    int s, e, m, v, ans, lz;
    node *l, *r;
    node(int _s, int _e, vector<int> &vec, vector<int> &qry) {
        s = _s, e = _e, m = (s+e)/2, lz = -1;
        if(s != e) {
            l = new node(s, m, vec, qry);
            r = new node(m+1, e, vec, qry);
            if(l->v == -1 || r->v == -1 || l->v != r->v) v = -1;
            else v = l->v;
            ans = l->ans & r->ans;
        } else {
            v = vec[s];
            ans = vec[s] == qry[s];
        }
    }
    void prop() {
        if(lz == -1) return;
        ans = lz == v;
        if(s != e) {
            l->lz = lz;
            r->lz = lz;
        }
        lz = -1;
    }
    void update(int x, int y, int val) {
        prop();
        if(x <= s && e <= y) {lz = val; return;}
        else if(x > m) r->update(x, y, val);
        else if(y <= m) l->update(x, y, val);
        else l->update(x, y, val), r->update(x, y, val);
        l->prop(); r->prop();
        ans = l->ans & r->ans;
    }
    int query() {
        prop();
        return ans;
    }
} *root[27];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, l, r, x;
    cin >> n;
    int a[3][n];
    string s;
    for(int j = 0; j < 3; j++) {
        cin >> s;
        for(int i = 0; i < n; i++) {
            if(s[i] == 'J') a[j][i] = 0;
            else if(s[i] == 'O') a[j][i] = 1;
            else a[j][i] = 2;
        }
    }
    vector<vector<int>> valid;
    for(int x = 0; x < 3; x++) {
        for(int y = 0; y < 3; y++) {
            for(int z = 0; z < 3; z++) {
                if((x+y+z)%3 != 1) continue;
                vector<int> v;
                for(int i = 0; i < n; i++) {
                    v.push_back((a[0][i]*x+a[1][i]*y+a[2][i]*z)%3);
                }
                valid.push_back(v);
            }
        }
    }
    cin >> q >> s;
    vector<int> vs;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'J') vs.push_back(0);
        else if(s[i] == 'O') vs.push_back(1);
        else vs.push_back(2);
    }
    int ans = 0;
    for(int i = 0; i < valid.size(); i++) {
        root[i] = new node(0, n-1, valid[i], vs);
        if(root[i]->query()) ans = 1;
    }
    cout << (ans?"Yes":"No") << '\n';
    char c;
    while(q--) {
        cin >> l >> r >> c;
        l--; r--;
        if(c == 'J') x = 0;
        else if(c == 'O') x = 1;
        else x = 2;
        ans = 0;
        for(int i = 0; i < valid.size(); i++) {
            root[i]->update(l, r, x);
            if(root[i]->query()) ans = 1;
        }
        cout << (ans?"Yes":"No") << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:83:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < valid.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:96:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i = 0; i < valid.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~

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