Submission #1268484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268484		k12_khoi	Crossing (JOI21_crossing)	C++17	26 / 100	357 ms	14900 KiB

Main

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

const int N=2e5+5;

int n,request,u,v,k,h,save,l,r;
int t[4*N][3],lazy[4*N][3],val[260];
char c;
string s,temp;
vector <int> ve[3];

void build(int id,int l,int r)
{
    t[id][h]=0;
    lazy[id][h]=-1;
    if (l==r) return;

    int m=(l+r)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);
}

void down(int id)
{
    if (lazy[id][h]!=-1)
    {
        lazy[id*2][h]=lazy[id][h];
        lazy[id*2+1][h]=lazy[id][h];

        t[id*2][h]=lazy[id][h];
        t[id*2+1][h]=lazy[id][h];

        lazy[id][h]=-1;
    }
}

void update(int id,int l,int r)
{
    if (u>r or v<l) return;
    if (u<=l and v>=r)
    {
        t[id][h]=k;
        lazy[id][h]=k;
        return;
    }
    down(id);

    int m=(l+r)/2;
    update(id*2,l,m);
    update(id*2+1,m+1,r);

    t[id][h]=t[id*2][h]|t[id*2+1][h];
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    val['J']=0;
    val['O']=1;
    val['I']=2;

    cin >> n;
    cin >> s;
    cin >> s;
    cin >> s;
    s='#'+s;

    for (int i=1;i<=n;i++)
    ve[val[s[i]]].push_back(i);

    cin >> request;
    cin >> temp;
    temp='#'+temp;

    for (h=0;h<=2;h++)
    if (!ve[h].empty())
        build(1,1,ve[h].size());

    for (int i=1;i<=n;i++)
    if (s[i]!=temp[i])
    {
        h=val[s[i]];

        u=lower_bound(ve[h].begin(),ve[h].end(),i)-ve[h].begin()+1;
        v=u;
        k=1;
        update(1,1,ve[h].size());
    }

    if (t[1][0] or t[1][1] or t[1][2]) cout << "No" << '\n';
    else cout << "Yes" << '\n';

    while (request--)
    {
        cin >> l >> r >> c;
        save=val[c];

        for (h=0;h<=2;h++)
        if (!ve[h].empty())
        {
            u=lower_bound(ve[h].begin(),ve[h].end(),l)-ve[h].begin()+1;
            v=upper_bound(ve[h].begin(),ve[h].end(),r)-ve[h].begin();
            k=(h!=save);
            update(1,1,ve[h].size());
        }

        if (t[1][0] or t[1][1] or t[1][2]) cout << "No" << '\n';
        else cout << "Yes" << '\n';
    }
}

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