제출 #936763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936763		ace5	Crossing (JOI21_crossing)	C++17	100 / 100	2174 ms	48072 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int mod = int(1e9)+7,pp = 101;

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

vector<int> segTree;
vector<int> p;
vector<int> st;

int binpow(int a,int b)
{
    return (b == 0 ? 1 : (b%2 == 0 ? binpow((a*a)%mod,b/2) : (a*binpow(a,b-1))%mod));
}
int del(int a,int b)
{
    return (a*binpow(b,mod-2))%mod;
}

int mrg(int a,int b,int lb,int rb)
{
    return (a*st[rb-lb+1]+ b)%mod;
}

void push(int l,int r,int indV)
{
    if(p[indV] == -1)
        return ;
    if(l == r)
    {
        segTree[indV] = p[indV];
        p[indV] = -1;
        return ;
    }
    segTree[indV] = (p[indV]*del((st[r-l+1]+mod-1)%mod,pp-1))%mod;
    p[indV*2+1] = p[indV];
    p[indV*2+2] = p[indV];
    p[indV] = -1;
    return ;
}

void modify(int lx,int rx,int x,int l,int r,int indV)
{
    push(l,r,indV);
    if(l > rx || r < lx)
        return ;
    else if(l >= lx && r <= rx)
    {
        p[indV] = x;
        push(l,r,indV);
        return ;
    }
    int m=(l+r)/2;
    modify(lx,rx,x,l,m,indV*2+1);
    modify(lx,rx,x,m+1,r,indV*2+2);
    segTree[indV] = mrg(segTree[indV*2+1],segTree[indV*2+2],m+1,r);
}
void print_ans(set<int> & hh)
{
    cout << (hh.find(segTree[0]) != hh.end() ? "Yes\n" : "No\n");
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    vector<vector<int>> s = {{},{},{}};
    string a,b,c;
    cin >> a >> b >> c;
    for(int i = 0;i < a.size();++i)
    {
        s[0].push_back(toint(a[i]));
    }
    for(int i = 0;i < b.size();++i)
    {
        s[1].push_back(toint(b[i]));
    }
    for(int i = 0;i < c.size();++i)
    {
        s[2].push_back(toint(c[i]));
    }
    set<vector<int>> ck;
    ck.insert(s[0]);
    ck.insert(s[1]);
    ck.insert(s[2]);
    while(true)
    {
        int u = s.size();
        for(int j =0;j < u;++j)
        {
            for(int i = j+1;i < u;++i)
            {
                vector<int> ne(n);
                for(int u = 0;u < n;++u)
                {
                    ne[u] = (s[i][u] == s[j][u] ? s[i][u] : 3-s[i][u]-s[j][u]);
                }
                if(ck.find(ne) == ck.end())
                {
                    ck.insert(ne);
                    s.push_back(ne);
                }
            }
        }
        if(s.size() == u)
            break;
    }
    set<int> hh;
    st.resize(n+1);
    st[0] = 1;
    for(int i =1;i <= n;++i)
    {
        st[i] = (st[i-1]*pp)%mod;
    }
    for(int j = 0;j < s.size();++j)
    {
        int th = 0;
        for(int k = 0;k < s[j].size();++k)
        {
            th *= pp;
            th += s[j][k];
            th = th%mod;
        }
        hh.insert(th);
    }
    segTree.resize(4*n);
    p.resize(4*n);
    for(int j = 0;j < 4*n;++j)
        p[j] = -1;
    int q;
    cin >> q;
    string t0;
    cin >> t0;
    for(int j = 0;j < t0.size();++j)
    {
        modify(j,j,toint(t0[j]),0,n-1,0);
    }
    print_ans(hh);
    while(q--)
    {
        int l,r;
        char c;
        cin >> l >> r >> c;
        int f = toint(c);
        modify(l-1,r-1,f,0,n-1,0);
        print_ans(hh);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0;i < a.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0;i < b.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0;i < c.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:116:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  116 |         if(s.size() == u)
      |            ~~~~~~~~~^~~~
Main.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int j = 0;j < s.size();++j)
      |                   ~~^~~~~~~~~~
Main.cpp:129:25: 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]
  129 |         for(int k = 0;k < s[j].size();++k)
      |                       ~~^~~~~~~~~~~~~
Main.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int j = 0;j < t0.size();++j)
      |                   ~~^~~~~~~~~~~

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