Submission #420015

#	Time	Username	Problem	Language	Result	Execution time	Memory
420015		Runtime_error_	Crossing (JOI21_crossing)	C++14	100 / 100	950 ms	28520 KiB

Main

//JOIOC 2021 p1 crossing
#include <bits/stdc++.h>
#define pb push_back
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 2e5+2,lg = 10;
int n,k,q;
bool ans;
string s;
vector<string> v;
int pre[lg][3][inf];
char ss[inf];
int mp[99];

string in(){
    scanf("%s",ss);
    return string(ss);
}

string cross(string &a,string &b){
    string ret = a;
    for(int i=0;i<n;i++){
        if(a[i] == b[i])
            continue;
        else if(a[i] != 'J' && b[i] != 'J')
            ret[i]= 'J';
        else if(a[i] != 'O' && b[i] != 'O')
            ret[i]= 'O';
        else
            ret[i]= 'I';
    }
    return ret;
}

void go(){
   map<string,bool> s;

    for(int i=0;i<3;i++)
        v.pb(in()),s[v.back()];
    v.pb(cross(v[0],v[1])),s[v.back()];
    v.pb(cross(v[0],v[2])),s[v.back()];
    v.pb(cross(v[1],v[2])),s[v.back()];

    s[cross(v[3],v[2])];
    s[cross(v[4],v[1])];
    s[cross(v[5],v[0])];

    v.clear();
    for(auto o:s)
        v.pb(o.first);
    k = v.size();
    for(int i=0;i<k;i++)
        for(int let=0;let<3;let++)
            for(int j=0;j<n;j++)
                    pre[i][let][j] = (j>0?pre[i][let][j-1]:0) + (mp[v[i][j]] == let);
}
int lazy[inf<<2],tree[inf<<2];

void build(int node,int l,int r){
    lazy[node] = -1;
    if(l == r){
        for(int i=0;i<k;i++)
            if(s[l] == v[i][l])
                tree[node] |= (1<<i);
        return;
    }
    build(le,l,mid);
    build(ri,mid+1,r);
    tree[node] = (tree[le] & tree[ri]);
}

void push(int node,int l,int r){
    if(lazy[node] == -1)
        return ;
    if(l != r)
        lazy[le] = lazy[ri] = lazy[node];

    int sz = r-l+1,let= lazy[node];
    tree[node] = 0;
    for(int i=0;i<k;i++)
        if((pre[i][let][r] - (l>0?pre[i][let][l-1]:0) ) == r-l+1 )
            tree[node] |= (1<<i);
    lazy[node] = -1;
}

void update(int node,int l,int r,int x,int y,int val){
    push(node,l,r);
    if(l>r || r<x || l>y || x>y)
        return ;
    if(l>=x && r<=y){
        lazy[node] = val;
        push(node,l,r);
        return ;
    }
    update(le,l,mid,x,y,val);
    update(ri,mid+1,r,x,y,val);
    tree[node] = (tree[le] & tree[ri]);
}

int main(){
    mp['J'] = 0,mp['O'] = 1,mp['I'] = 2;
    scanf("%d",&n);
    go();
    assert(k<lg);
    scanf("%d",&q);
    s = in();
    ans = 0;
    build(1,0,n-1);
    if(tree[1])
        puts("Yes");
    else
        puts("No");
    while(q--){
        int l,r;
        ans =0;
        char c[2];
        scanf("%d%d",&l,&r);
        scanf("%s",c);
        update(1,0,n-1,l-1,r-1,mp[c[0]]);
    if(tree[1])
        puts("Yes");
    else
        puts("No");
    }
}

Compilation message (stderr)

Main.cpp: In function 'void go()':
Main.cpp:58:76: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |                     pre[i][let][j] = (j>0?pre[i][let][j-1]:0) + (mp[v[i][j]] == let);
      |                                                                            ^
Main.cpp: In function 'void push(int, int, int)':
Main.cpp:81:9: warning: unused variable 'sz' [-Wunused-variable]
   81 |     int sz = r-l+1,let= lazy[node];
      |         ^~
Main.cpp: In function 'int main()':
Main.cpp:122:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  122 |         update(1,0,n-1,l-1,r-1,mp[c[0]]);
      |                                   ~~~^
Main.cpp: In function 'std::string in()':
Main.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%s",ss);
      |     ~~~~~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         scanf("%s",c);
      |         ~~~~~^~~~~~~~

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