Submission #780756

#	Time	Username	Problem	Language	Result	Execution time	Memory
780756		Rafi22	Crossing (JOI21_crossing)	C++14	100 / 100	2470 ms	195656 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

map<vector<int>,bool>odw;

const int N=200007,pot=1<<18;

int a[N][3];
int b[N][9];
int id[300];

struct tree
{
    int seg[2*pot+7],cnt[2*pot+7][3],lzy[2*pot+7];
    tree()
    {
        memset(seg,0,sizeof seg);
        memset(cnt,0,sizeof cnt);
    }
    void push(int v)
    {
        if(lzy[v]!=-1)
        {
            seg[2*v]=cnt[2*v][lzy[v]];
            lzy[2*v]=lzy[v];
            seg[2*v+1]=cnt[2*v+1][lzy[v]];
            lzy[2*v+1]=lzy[v];
        }
        lzy[v]=-1;
    }
    void upd(int v,int a,int b,int l,int r,int x)
    {
        if(a<=l&&b>=r)
        {
            seg[v]=cnt[v][x];
            lzy[v]=x;
            return;
        }
        if(r<a||l>b) return ;
        push(v);
        upd(2*v,a,b,l,(l+r)/2,x);
        upd(2*v+1,a,b,(l+r)/2+1,r,x);
        seg[v]=seg[2*v]+seg[2*v+1];
    }
};


int n;
vector<tree>T;
void get()
{
    bool ans=0;
    for(int j=0;j<9;j++)
    {
        if(T[j].seg[1]==n) ans=1;
    }
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector<vector<int>>V;
    V.pb({1,0,0});
    odw[{1,0,0}]=1;
    V.pb({0,1,0});
    odw[{0,1,0}]=1;
    V.pb({0,0,1});
    odw[{0,0,1}]=1;
    for(int i=0;i<sz(V);i++)
    {
        for(int j=0;j<i;j++)
        {
            vector<int>X(3);
            for(int l=0;l<3;l++)
            {
                X[l]=(-V[i][l]-V[j][l]+6)%3;
            }
            if(!odw[X])
            {
                V.pb(X);
                odw[X]=1;
            }
        }
    }
    id['J']=0;
    id['O']=1;
    id['I']=2;
    cin>>n;
    string s;
    for(int j=0;j<3;j++)
    {
        cin>>s;
        for(int i=1;i<=n;i++) a[i][j]=id[s[i-1]];
    }
    for(int j=0;j<9;j++)
    {
        tree X;
        for(int i=1;i<=n;i++)
        {
            for(int l=0;l<3;l++)
            {
                b[i][j]=(b[i][j]+a[i][l]*V[j][l])%3;
            }
            X.cnt[i+pot-1][b[i][j]]=1;
        }
        for(int i=pot-1;i>0;i--)
        {
            for(int j=0;j<3;j++) X.cnt[i][j]=X.cnt[2*i][j]+X.cnt[2*i+1][j];
        }
        for(int i=1;i<2*pot;i++) X.lzy[i]=-1;
        T.pb(X);
    }
    int q;
    cin>>q>>s;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<9;j++) T[j].upd(1,i,i,1,pot,id[s[i-1]]);
    }
    get();
    while(q--)
    {
        int l,r;
        char x;
        cin>>l>>r>>x;
        for(int j=0;j<9;j++) T[j].upd(1,l,r,1,pot,id[x]);
        get();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:109:48: warning: array subscript has type 'char' [-Wchar-subscripts]
  109 |         for(int i=1;i<=n;i++) a[i][j]=id[s[i-1]];
      |                                                ^
Main.cpp:133:60: warning: array subscript has type 'char' [-Wchar-subscripts]
  133 |         for(int j=0;j<9;j++) T[j].upd(1,i,i,1,pot,id[s[i-1]]);
      |                                                            ^
Main.cpp:141:54: warning: array subscript has type 'char' [-Wchar-subscripts]
  141 |         for(int j=0;j<9;j++) T[j].upd(1,l,r,1,pot,id[x]);
      |                                                      ^

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