Submission #866690

#	Time	Username	Problem	Language	Result	Execution time	Memory
866690		vjudge1	Crossing (JOI21_crossing)	C++17	100 / 100	2282 ms	100836 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int const MAXN=2e6, K=(1<<18);

int n, q;
string a, b, c, p;
vector<string> v;
bool tree[10][2*K-1];
char lazy[10][2*K-1];
int jprefix[10][MAXN], oprefix[10][MAXN], iprefix[10][MAXN];

string cross(string a, string b)
{
    string t=a;
    for (int i=0; i<a.size(); i++)
    {
        if (a[i]==b[i])
            t[i]=a[i];
        if (b[i]<a[i])
            swap(a[i], b[i]);
        if (a[i]=='I' && b[i]=='J')
            t[i]='O';
        if (a[i]=='I' && b[i]=='O')
            t[i]='J';
        if (a[i]=='J' && b[i]=='O')
            t[i]='I';
    }

    return t;
}

bool goodstring()
{
    for (int j=0; j<v.size(); j++)
        if (tree[j][0])
            return true;

    return false;
}

bool good(int j, int l, int r, char c)
{
    r=min(r, n)-1;
    if (l>r)
        return true;
    int total;
    if (c=='J')
    {
        total=jprefix[j][r];
        if (l!=0)
            total=total-jprefix[j][l-1];
    }
    if (c=='O')
    {
        total=oprefix[j][r];
        if (l!=0)
            total=total-oprefix[j][l-1];
    }
    if (c=='I')
    {
        total=iprefix[j][r];
        if (l!=0)
            total=total-iprefix[j][l-1];
    }

    return total==r-l+1;
}

void propagate(int j, int x, int l, int r)
{
    if (lazy[j][x]=='#')
        return;
    if (r-l==1)
    {
        lazy[j][x]='#';
        return;
    }
    tree[j][2*x+1]=good(j, l, (l+r)/2, lazy[j][x]);
    lazy[j][2*x+1]=lazy[j][x];
    tree[j][2*x+2]=good(j, (l+r)/2, r, lazy[j][x]);
    lazy[j][2*x+2]=lazy[j][x];
    lazy[j][x]='#';

    return;
}

void update(int j, int x, int l, int r, char c, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return;
    if (l>=lt && r<=rt)
    {
        tree[j][x]=good(j, l, r, c);
        lazy[j][x]=c;
        return;
    }
    propagate(j, x, l, r);
    update(j, 2*x+1, l, (l+r)/2, c, lt, rt);
    update(j, 2*x+2, (l+r)/2, r, c, lt, rt);
    if (r-l==1)
    {
        if (l>=n)
            tree[j][x]=true;
        else
            tree[j][x]=(v[j][l]==c);
    }
    else
        tree[j][x]=(tree[j][2*x+1]&tree[j][2*x+2]);

    return;
}

int main()
{
    cin >> n >> a >> b >> c;
    cin >> q >> p;

    set<string> s, snew;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    bool newstring=true;
    while (newstring)
    {
        newstring=false;
        snew.clear();
        for (int i=0; i<v.size(); i++)
            for (int j=i+1; j<v.size(); j++)
            {
                string t=cross(v[i], v[j]);
                if (s.count(t)==0)
                {
                    snew.insert(t);
                    newstring=true;
                }
            }
        for (auto t : snew)
        {
            s.insert(t);
            v.push_back(t);
        }
    }

    for (int j=0; j<v.size(); j++)
        for (int i=0; i<2*K-1; i++)
        {
            tree[j][i]=true;
            lazy[j][i]='#';
        }
    for (int j=0; j<v.size(); j++)
    {
        jprefix[j][0]=0;
        oprefix[j][0]=0;
        iprefix[j][0]=0;
        if (v[j][0]=='J')
            jprefix[j][0]=1;
        if (v[j][0]=='O')
            oprefix[j][0]=1;
        if (v[j][0]=='I')
            iprefix[j][0]=1;
        for (int i=1; i<n; i++)
        {
            jprefix[j][i]=jprefix[j][i-1];
            oprefix[j][i]=oprefix[j][i-1];
            iprefix[j][i]=iprefix[j][i-1];
            if (v[j][i]=='J')
                jprefix[j][i]=jprefix[j][i]+1;
            if (v[j][i]=='O')
                oprefix[j][i]=oprefix[j][i]+1;
            if (v[j][i]=='I')
                iprefix[j][i]=iprefix[j][i]+1;
        }
    }

    for (int j=0; j<v.size(); j++)
        for (int i=0; i<n; i++)
            update(j, 0, 0, K, p[i], i, i+1);
    if (goodstring())
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    while (q--)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        l=l-1;
        for (int j=0; j<v.size(); j++)
            update(j, 0, 0, K, c, l, r);
        if (goodstring())
            cout << "Yes" << '\n';
        else
            cout << "No" << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0; i<a.size(); i++)
      |                   ~^~~~~~~~~
Main.cpp: In function 'bool goodstring()':
Main.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j=0; j<v.size(); j++)
      |                   ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (int i=0; i<v.size(); i++)
      |                       ~^~~~~~~~~
Main.cpp:132:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int j=i+1; j<v.size(); j++)
      |                             ~^~~~~~~~~
Main.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int j=0; j<v.size(); j++)
      |                   ~^~~~~~~~~
Main.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (int j=0; j<v.size(); j++)
      |                   ~^~~~~~~~~
Main.cpp:179:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for (int j=0; j<v.size(); j++)
      |                   ~^~~~~~~~~
Main.cpp:193:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for (int j=0; j<v.size(); j++)
      |                       ~^~~~~~~~~
Main.cpp: In function 'bool good(int, int, int, char)':
Main.cpp:67:23: warning: 'total' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     return total==r-l+1;
      |                       ^

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