Submission #1015527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015527		daffuwu	Crossing (JOI21_crossing)	C++14	0 / 100	67 ms	928 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long n, sz, q, l, r, pw3[200069][2], ps[200069][2], sm[2];
const long long dv[] = {1000000007, 1000000009};
pair<long long, long long> ans;
bool bad;
char ch;
string s[3], cs, t0;
vector<string> ls;
map<char, long long> conv;
map<string, bool> ex;
map<pair<long long, long long>, bool> hsh;

char crot(char a, char b)
{
    if (a>b) swap(a, b);
    if (a == b) return a;
    if (a == 'I' && b == 'J') return 'O';
    if (a == 'I' && b == 'O') return 'J';
    return 'I';
}

string cross(string a, string b)
{
    int i;
    string c = "";
    for (i=0; i<n; i++)
    {
        c += crot(a[i], b[i]);
    }
    return c;
}

long long calc(long long l, long long r, long long id)
{
    //3^l+3^(l+1)+...+3^r
    if (l == 0) return ps[r][id];
    return (ps[r][id]-ps[l-1][id]+dv[id])%dv[id];
}

struct segtree
{
    long long l, r, val[2], lz = -1;
    segtree *le, *ri;

    void bd(long long cl, long long cr)
    {
        l = cl;
        r = cr;
        if (cl == cr)
        {
            val[0] = conv[t0[cl-1]]*pw3[cl-1][0]%dv[0];
            val[1] = conv[t0[cl-1]]*pw3[cl-1][1]%dv[1];
            return;
        }
        long long md = (cl+cr)/2;
        le = new segtree();
        ri = new segtree();
        le->bd(cl, md);
        ri->bd(md+1, cr);
        val[0] = (le->val[0]+ri->val[0])%dv[0];
        val[1] = (le->val[1]+ri->val[1])%dv[1];
    }

    void prop()
    {
        if (lz != -1)
        {
            val[0] = calc(l-1, r-1, 0)*lz%dv[0];
            val[1] = calc(l-1, r-1, 1)*lz%dv[1];
            if (l != r)
            {
                le->lz = lz;
                ri->lz = lz;
            }
            lz = -1;
        }
    }

    void upd(long long ql, long long qr, long long x)
    {
        prop();
        if (l>qr || r<ql) return;
        if (l>=ql && r<=qr)
        {
            lz = x;
            prop();
            return;
        }
        le->upd(ql, qr, x);
        ri->upd(ql, qr, x);
        val[0] = (le->val[0]+ri->val[0])%dv[0];
        val[1] = (le->val[1]+ri->val[1])%dv[1];
    }

    pair<long long, long long> qry(long long ql, long long qr)
    {
        prop();
        if (l>qr || r<ql) return {0, 0};
        if (l>=ql && r<=qr) return {val[0], val[1]};
        pair<long long, long long> pl = le->qry(ql, qr), pr = ri->qry(ql, qr);
        return {(pl.fr+pr.fr)%dv[0], (pl.sc+pr.sc)%dv[1]};
    }
} *rt;

int main() 
{
    long long i, j, rr;
    scanf("%lld", &n);
    pw3[0][0] = pw3[0][1] = ps[0][0] = ps[0][1] = 1;
    conv['I'] = 0;
    conv['J'] = 1;
    conv['O'] = 2;
    for (i=1; i<n; i++)
    {
        for (j=0; j<=1; j++)
        {
            pw3[i][j] = pw3[i-1][j]*3%dv[j];
            ps[i][j] = (ps[i-1][j]+pw3[i][j])%dv[j];
        }
    } 
    cin >> s[0] >> s[1] >> s[2]; 
    ex[s[0]] = ex[s[1]] = ex[s[2]] = 1;
    for (auto [ky, _]:ex) ls.push_back(ky);
    for (; 1;)
    {
        sz = ls.size();
        bad = 1;
        for (i=0; i<sz; i++)
        {
            for (j=i+1; j<sz; j++)
            {
                cs = cross(ls[i], ls[j]);
                if (!ex.count(cs))
                {
                    ex[cs] = 1;
                    bad = 0;
                    i = sz+1;
                    break;
                }
            }
        }
        if (bad) break;
        ls.push_back(cs);
    }
    for (auto el:ls)
    {
        for (j=0; j<=1; j++)
        {
            sm[j] = 0;
            for (i=0; i<n; i++)
            {
                sm[j] += pw3[i][j]*conv[el[i]];
                sm[j] %= dv[j];
            }
        }
        hsh[{sm[0], sm[1]}] = 1;
    }
    rt = new segtree();
    scanf("%lld", &q);
    for (rr=0; rr<=q; rr++)
    {
        if (rr == 0)
        {
            cin >> t0;
            rt->bd(1, n);
        }
        else 
        {
            scanf("%lld%lld %c", &l, &r, &ch);
            rt->upd(l, r, conv[ch]);
        }
        ans = rt->qry(1, n);
        if (hsh.count(ans)) printf("Yes\n");
        else printf("No\n");
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for (auto [ky, _]:ex) ls.push_back(ky);
      |               ^
Main.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |     scanf("%lld", &q);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |             scanf("%lld%lld %c", &l, &r, &ch);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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