Submission #1086291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086291		phong	Crossing (JOI21_crossing)	C++17	100 / 100	272 ms	33036 KiB

Main

#include<bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7, mod2 = 1e9+3;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;



int n;
int a[5][nmax];
pii get(vector<int> &tmp){
    pii tx = {0, 0};
    for(auto p : tmp){
        tx.fi = (tx.fi * base + p) % mod;
        tx.se = (tx.se * base + p) % mod2;
    }
    return tx;
}
map<pii, int> vis;
vector<pii>lol;
void dfs(vector<int> tmp){
    vis[get(tmp)] = 1;
    vector<int> one;
    if(tmp.size()) lol.push_back(get(tmp));
    for(int i = 1; i <= 3; ++i){
        one.clear();
        if(tmp.empty()){
            for(int j = 1;j <= n; ++j) one.push_back(a[i][j]);
        }
        else{
            for(int j = 1; j <= n; ++j){
                if(tmp[j - 1] == a[i][j]) one.push_back(tmp[j - 1]);
                else one.push_back(tmp[j - 1] ^ a[i][j]);
            }
        }
        if(vis[get(one)]) continue;
        dfs(one);
    }
}
int s[nmax];
pii tree[nmax << 2];
pii h[5][nmax];
ll pw[5][nmax];
int G[nmax << 2], lz[nmax << 2];

void build(int id, int l, int r){
    G[id] = r - l + 1;
    if(l == r){
        tree[id] = {s[l], s[l]};
        return;
    }
    int mid =r + l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    tree[id].fi = (tree[id << 1].fi * pw[0][r - mid] + tree[id << 1 | 1].fi) % mod;
    tree[id].se = (tree[id << 1].se * pw[1][r - mid] + tree[id << 1 | 1].se) % mod2;
}
void fix(int id, int val){
    if(val == 0) return;
    int x = G[id];
    tree[id] = h[val][x];
    lz[id] = val;
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int k){
    if(l > v || r < u) return;
    if(l >= u && r <= v){
//        cout << k << ' ';
        return fix(id, k);
    }
    down(id);
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, v, k);
    update(id << 1 | 1, mid + 1, r, u, v, k);
    tree[id].fi = (tree[id << 1].fi * pw[0][r - mid] + tree[id << 1 | 1].fi) % mod;
    tree[id].se = (tree[id << 1].se * pw[1][r - mid] + tree[id << 1 | 1].se) % mod2;
}

bool check(){
    for(auto p : lol) if(tree[1] == p) return 1;
    return 0;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= 3; ++i){
        for(int j = 1; j <= n; ++j){
            char x;
            cin >> x;
            if(x == 'J') a[i][j] = 1;
            else if(x == 'O') a[i][j] = 2;
            else a[i][j] = 3;
        }
    }
    vector<int> tmp;
    dfs(tmp);
    int q;cin >> q;
    int cur = 0;
    for(int i = 1; i <= n; ++i){
        char x;
        cin >> x;
        if(x == 'J')s[i] = 1;
        else if(x == 'O')s[i] = 2;
        else s[i] = 3;
    }

    pw[0][0] = pw[1][0] = 1;
    for(int i = 1; i <= n; ++i){
        pw[0][i] = pw[0][i - 1] * base % mod;
        pw[1][i] = pw[1][i - 1] * base % mod2;
    }
    for(int e = 1; e <= 3; ++e){
        pii tx = {0, 0};
        for(int i = 1; i <= n; ++i){
            tx.fi = (tx.fi * base + e) % mod;
            tx.se = (tx.se * base + e) % mod2;
            h[e][i] = tx;
        }
    }

    build(1, 1, n);

    if(check()) cout << "Yes";
    else cout << "No";
    cout << endl;
    while(q--){
        int l, r, k;
        char x;
        cin >> l >> r >> x;
        if(x == 'J')k = 1;
        else if(x == 'O')k= 2;
        else k= 3;
        update(1, 1, n, l, r, k);
        if(check()) cout << "Yes";
        else cout << "No";
        cout << endl;
    }

}
/*
4
JOJO
JJOI
OJOO
1
OOOO
1 4 O
2 2 J
2 4 I



*/

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:59:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid =r + l >> 1;
      |              ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = r + l >> 1;
      |               ~~^~~
Main.cpp: At global scope:
Main.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:112:9: warning: unused variable 'cur' [-Wunused-variable]
  112 |     int cur = 0;
      |         ^~~

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