Submission #936385

#	Time	Username	Problem	Language	Result	Execution time	Memory
936385		ace5	Crossing (JOI21_crossing)	C++17	26 / 100	7011 ms	37388 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

int getint(char c)
{
    return (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
}

struct Streq
{
    Streq(vector<int> _et,vector<int> _cur){et = _et;cur = _cur;};
    Streq(){et = {};cur = {};};
    vector<int> et;
    vector<int> cur;

    bool isGood()
    {
        return et == cur;
    }

    void modify(int l,int r,int f)
    {
        for(int i = l;i <= r;++i)
        {
            cur[i] = f;
        }
    }
};

vector<vector<Streq>> ms(5,vector<Streq>(3));

bool can_get()
{
    bool no = 0;
    for(int i = 0;i < 5;++i)
    {
        bool y = 0;
        for(int j = 0;j < 3;++j)
        {
            if(ms[i][j].isGood())
                y = 1;
        }
        if(!y)
            no = 1;
    }
    return !no;
}
void print_ans()
{
    cout << (can_get() ? "Yes\n" : "No\n");
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string aa,bb,cc;
    cin >> aa >> bb >> cc;
    vector<int> a(n),b(n),c(n);
    for(int i = 0;i < n;++i)
    {
        a[i] = getint(aa[i]);
        b[i] = getint(bb[i]);
        c[i] = getint(cc[i]);
    }
    vector<vector<int>> ix(5);
    vector<vector<int>> ind;
    for(int i = 0;i < n;++i)
    {
        if(a[i] == b[i] && a[i] != c[i])
        {
            ix[0].push_back(i);
            ind.push_back({a[i],c[i],3 - a[i] - c[i]});
        }
        if(a[i] == c[i] && a[i] != b[i])
        {
            ix[1].push_back(i);
            ind.push_back({a[i],b[i],3 - a[i] - b[i]});
        }
        if(c[i] == b[i] && a[i] != c[i])
        {
            ix[2].push_back(i);
            ind.push_back({b[i],a[i],3 - a[i] - b[i]});
        }
        if(a[i] != b[i] && a[i] != c[i] && b[i] != c[i])
        {
            ix[3].push_back(i);
            ind.push_back({a[i],b[i],c[i]});
        }
        if(a[i] == b[i] && b[i] ==c[i])
        {
            ix[4].push_back(i);
            ind.push_back({a[i],a[i],a[i]});
        }
    }
    int q;
    cin >> q;
    string t0;
    cin >> t0;
    for(int i = 0;i < 5;++i)
    {
        for(int j = 0;j < 3;++j)
        {
            vector<int> tet,tcur;
            for(int k = 0;k < ix[i].size();++k)
            {
                tet.push_back(ind[ix[i][k]][j]);
                tcur.push_back(getint(t0[ix[i][k]]));
            }
            ms[i][j].et = tet;
            ms[i][j].cur = tcur;
        }
    }
    print_ans();
    while(q--)
    {
        int l,r;
        char cc;
        cin >> l >> r >> cc;
        l--;
        r--;
        int f = getint(cc);
        for(int i = 0;i < 5;++i)
        {
            int lg = lower_bound(ix[i].begin(),ix[i].end(),l)-ix[i].begin();
            int rg = upper_bound(ix[i].begin(),ix[i].end(),r)-ix[i].begin()-1;
            for(int j = 0;j < 3;++j)
                ms[i][j].modify(lg,rg,f);
        }
        print_ans();
    }
}

Compilation message (stderr)

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

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