Submission #479620

#	Time	Username	Problem	Language	Result	Execution time	Memory
479620		nicolaalexandra	Crossing (JOI21_crossing)	C++14	100 / 100	1212 ms	38132 KiB

Main

#include <bits/stdc++.h>
#define DIM 200010
#define MOD1 1000000007
#define MOD2 1000000009
using namespace std;

struct segment_tree{
    long long hash1,hash2;
    int lazy;
} aint[DIM*4];

string a,b,c,v,aux;
deque <string> d,w;
map <pair<long long,long long>, int> f;
int poz[DIM];
long long p1[DIM],p2[DIM],sp1[DIM],sp2[DIM];
int n,i,j,x,y,q;
char ch;

int convert (char ch){
    if (ch == 'J')
        return 1;
    if (ch == 'O')
        return 2;
    return 3;
}

pair <long long,long long> get_hash (string s){

    long long hash1 = 0, hash2 = 0;
    for (int i=0;i<n;i++){

        int val = convert(s[i]);

        hash1 = (hash1 * 4 % MOD1 + val) % MOD1;
        hash2 = (hash2 * 4 % MOD2 + val) % MOD2;
    }

    return make_pair (hash1,hash2);
}

void crossing (string a, string b){
    for (int i=0;i<n;i++){
        if (a[i] == b[i])
            aux[i] = a[i];
        else {
            if (a[i] != 'J' && b[i] != 'J')
                aux[i] = 'J';
            else {
                if (a[i] != 'O' && b[i] != 'O')
                    aux[i] = 'O';
                else aux[i] = 'I';
            }}}}

void update_nod (int nod, int st, int dr){
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    int mid = (st+dr)>>1;

    aint[nod].hash1 = (aint[fiu_st].hash1 * p1[dr-mid] + aint[fiu_dr].hash1) % MOD1;
    aint[nod].hash2 = (aint[fiu_st].hash2 * p2[dr-mid] + aint[fiu_dr].hash2) % MOD2;

}

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;

    if (st != dr){
        int mid = (st+dr)>>1;
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;

        aint[fiu_st].hash1 = 1LL * aint[nod].lazy * sp1[mid-st] % MOD1;
        aint[fiu_st].hash2 = 1LL * aint[nod].lazy * sp2[mid-st] % MOD2;
        aint[fiu_st].lazy = aint[nod].lazy;

        aint[fiu_dr].hash1 = 1LL * aint[nod].lazy * sp1[dr-mid-1] % MOD1;
        aint[fiu_dr].hash2 = 1LL * aint[nod].lazy * sp2[dr-mid-1] % MOD2;
        aint[fiu_dr].lazy = aint[nod].lazy;

    }

    aint[nod].lazy = 0;
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].hash1 = aint[nod].hash2 = convert (v[st-1]);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    update_nod (nod,st,dr);
}

void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){

        aint[nod].hash1 = 1LL * val * sp1[dr-st] % MOD1;
        aint[nod].hash2 = 1LL * val * sp2[dr-st] % MOD2;

        aint[nod].lazy = val;

        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    update_nod (nod,st,dr);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    cin>>a>>b>>c;

    d.push_back(a);
    f[get_hash(a)] = 1;
    poz[0] = 0;

    pair<long long,long long> val = get_hash(b);
    if (!f[val]){
        f[val] = 1;
        d.push_back(b);
        poz[1] = 1;
    }

    val = get_hash(c);

    if (!f[val]){
        f[val] = 1;
        d.push_back(c);
        poz[2] = 2;
    }

    for (i=1;i<=n;i++)  /// nus cum sa declar un string care sa nu fie gol
        aux += "J";

    for (;;){
        w.clear();
        for (i=0;i<d.size();i++){
            for (j=poz[i]+1;j<d.size();j++){
                crossing (d[i],d[j]);

                pair <long long,long long> val = get_hash(aux);
                if (!f[val]){
                    w.push_back(aux);
                    f[val] = 1;
                }

            }
            poz[i] = d.size()-1;
        }

        if (w.empty())
            break;

        for (auto it : w)
            d.push_back(it);
    }


    cin>>q;
    cin>>v;

    p1[0] = p2[0] = 1;
    sp1[0] = sp2[0] = 1;
    for (i=1;i<=n;i++){
        p1[i] = p1[i-1] * 4 % MOD1;
        p2[i] = p2[i-1] * 4 % MOD2;

        sp1[i] = (sp1[i-1] + p1[i]) % MOD1;
        sp2[i] = (sp2[i-1] + p2[i]) % MOD2;
    }



    build (1,1,n);

    if (f[make_pair(aint[1].hash1,aint[1].hash2)])
        cout<<"Yes\n";
    else cout<<"No\n";

    for (;q--;){
        cin>>x>>y>>ch;

        int val = convert(ch);

        update (1,1,n,x,y,val);

        if (f[make_pair(aint[1].hash1,aint[1].hash2)])
            cout<<"Yes\n";
        else cout<<"No\n";
    }


    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:153:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for (i=0;i<d.size();i++){
      |                  ~^~~~~~~~~
Main.cpp:154:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for (j=poz[i]+1;j<d.size();j++){
      |                             ~^~~~~~~~~

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