Submission #936732

#	Time	Username	Problem	Language	Result	Execution time	Memory
936732		ace5	Crossing (JOI21_crossing)	C++17	49 / 100	3092 ms	93544 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 SegTree3
{
    SegTree3(vector<int> _a){a = _a;};
    SegTree3(){a = {};};

    vector<int> a;

    void modify(int i,int x,int l,int r,int indV)
    {
        if(l > i || r < i)
            return ;
        else if(l == r)
        {
            a[indV] = x;
            return ;
        }
        int m = (l+r)/2;
        modify(i,x,l,m,indV*2+1);
        modify(i,x,m+1,r,indV*2+2);
        a[indV] = (a[indV*2+1] == a[indV*2+2] ? a[indV*2+1] : -1);
        return ;
    }
    int get(int lx,int rx,int l,int r,int indV)
    {
        if(l > rx || r < lx)
            return 4;
        else if(l >= lx && r <= rx)
            return a[indV];
        int m = (l+r)/2;
        int sl = get(lx,rx,l,m,indV*2+1);
        int sr = get(lx,rx,m+1,r,indV*2+2);
        return (sl == 4 ? sr : (sr == 4 ? sl : (sl == sr ? sl : -1)));
    }
};

struct Streq
{
    Streq(SegTree3 _et,set<pair<pair<int,int>,pair<int,int>>> _seg){et = _et;seg = _seg;};
    Streq(){et = SegTree3();seg = {};};
    SegTree3 et;
    set<pair<pair<int,int>,pair<int,int>>> seg;
    int kps =  0;
    int ts = 0;

    bool isGood()
    {
        return kps == 0;
    }
    void modify(int l,int r,int f)
    {
        if(l > r)
            return ;
        while(true)
        {
           // cout << 1 << endl;
           // cout << seg.size() << "\n";
            auto it = seg.lower_bound(make_pair(make_pair(l,1e6),make_pair(1e6,1e6)));
            if(it != seg.begin())
            {
                it--;
            }
            if(it == seg.end())
                break;
            pair<pair<int,int>,pair<int,int>> cur = *it;
            if(max(cur.first.first,l) > min(cur.first.second,r))
            {
               // cout << "!" << endl;
                it++;
               // cout << "!" << endl;
                if(it != seg.end())
                    cur = *it;
            }
           // cout << "!" << endl;
            if(max(cur.first.first,l) > min(cur.first.second,r))
                break;
           // cout << 2 << endl;
            kps -= (cur.second.second == 1);
            seg.erase(it);
            if(cur.first.first < l && cur.first.second > r)
            {
                pair<int,int> o1 = {cur.first.first,l-1};
                pair<int,int> o2 = {r+1,cur.first.second};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                bool g2 = (et.get(o2.first,o2.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);
                }
                if(o2.first <= o2.second)
                {
                    seg.insert({o2,{cur.second.first,!g2}});
                    kps += (!g2);
                }
            }
            else if(cur.first.second > r)
            {
                pair<int,int> o1 = {r+1,cur.first.second};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);

                }
            }
            else if(cur.first.first < l)
            {
                pair<int,int> o1 = {cur.first.first,l-1};
                bool g1 = (et.get(o1.first,o1.second,0,ts-1,0) == cur.second.first);
                if(o1.first <= o1.second)
                {
                    seg.insert({o1,{cur.second.first,!g1}});
                    kps += (!g1);
                }
            }
           // cout << 3 << endl;
        }
       // cout << "!" << endl;
        bool gg = (et.get(l,r,0,ts-1,0) == f);
        seg.insert({{l,r},{f,!gg}});
        kps += (!gg);
      //  cout << kps << "\n";
       // cout << "!" << endl;
    }
};

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.a.resize(4*tet.size());
            ms[i][j].ts = tet.size();
            for(int k = 0;k < tet.size();++k)
            {
                ms[i][j].et.modify(k,tet[k],0,int(tet.size())-1,0);
            }

            for(int k = 0;k < tet.size();++k)
            {
                ms[i][j].seg.insert({{k,k},{tcur[k],tcur[k] != tet[k]}});
                ms[i][j].kps += (tcur[k] != tet[k]);
            }
        }
    }
    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:217: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]
  217 |             for(int k = 0;k < ix[i].size();++k)
      |                           ~~^~~~~~~~~~~~~~
Main.cpp:224: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]
  224 |             for(int k = 0;k < tet.size();++k)
      |                           ~~^~~~~~~~~~~~
Main.cpp:229: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]
  229 |             for(int k = 0;k < tet.size();++k)
      |                           ~~^~~~~~~~~~~~

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