Submission #1084204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084204		yoav_s	Crossing (JOI21_crossing)	C++17	100 / 100	3021 ms	31996 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

v process(v &a, v &b)
{
    ll N = a.size();
    v res(N);
    for (ll i = 0; i < N; i++)
    {
        if (a[i] == b[i]) res[i] = a[i];
        else res[i] = 3 - a[i] - b[i];
    }
    return res;
}

ll toNumber(v &a)
{
    ll cur = 1;
    ll res = 0;
    for (ll x: a)
    {
        res += x * cur;
        cur *= 3;
    }
    return res;
}

vb getReachable(vp &classes)
{
    ll n = classes.size();
    vv reachable;
    reachable.pb(v(n, 0));
    v a(n), b(n);
    for (ll i = 0; i < n; i++)
    {
        a[i] = classes[i].f;
        b[i] = classes[i].s;
    }
    reachable.pb(a);
    reachable.pb(b);
    ll maxi = 1;
    for (ll i = 0; i < n; i++) maxi *= 3;
    vb visited(maxi, false);
    for (auto x : reachable) visited[toNumber(x)] = true;
    for (ll i = 0; i < reachable.size(); i++)
    {
        for (ll j = 0; j < i; j++)
        {
            v cur = process(reachable[i], reachable[j]);
            if (visited[toNumber(cur)]) continue;
            visited[toNumber(cur)] = true;
            reachable.pb(cur);
        }
    }
    return visited;
}

ll getAmt(ll l, ll r, v &arr)
{
    return upper_bound(all(arr), r) - lower_bound(all(arr), l);
}

vv getInvalid(ll l, ll r, vvv &classExpectation, ll equalTo)
{
    ll classCnt = classExpectation.size();
    vv res(classCnt, v(3, 0));
    for (ll i = 0; i < classCnt; i++)
    {
        v actAmt(3);
        for (ll j = 0; j < 3; j++) actAmt[j] = getAmt(l, r, classExpectation[i][j]);
        for (ll j = 0; j < 3; j++)
        {
            for (ll k = 0; k < 3; k++)
            {
                if (j != (equalTo + k) % 3) res[i][j] += actAmt[k];
            }
        }
    }
    return res;
}

void add(vv &a, vv b)
{
    for (ll i = 0; i < a.size(); i++)
    {
        for (ll j = 0; j < a[0].size(); j++)
        {
            a[i][j] += b[i][j];
        }
    }
}

void substract(vv &a, vv b)
{
    for (ll i = 0; i < a.size(); i++)
    {
        for (ll j = 0; j < a[0].size(); j++)
        {
            a[i][j] -= b[i][j];
        }
    }
}

bool checkValidity(vv &notMatchingCnt, vb &reachable)
{
    ll n = notMatchingCnt.size();
    v chosen(n, -1);
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < 3; j++) if (notMatchingCnt[i][j] == 0) chosen[i] = j;
        if (chosen[i] == -1) return false;
    }
    return reachable[toNumber(chosen)];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N;
    cin >> N;
    string sA, sB, sC;
    cin >> sA >> sB >> sC;
    map<char, ll> conv{{'J',0},{'O',1},{'I',2}};
    v a(N), b(N), c(N);
    for (ll i = 0; i < N; i++)
    {
        a[i] = conv[sA[i]];
        b[i] = conv[sB[i]];
        c[i] = conv[sC[i]];
    }
    v aNormalized(N), bNormalized(N), cNormalized(N);
    v offset(N);
    for (ll i = 0; i < N; i++)
    {
        aNormalized[i] = 0;
        bNormalized[i] = (b[i] - a[i] + 3) % 3;
        cNormalized[i] = (c[i] - a[i] + 3) % 3;
        offset[i] = (3 - a[i]) % 3;
    }
    map<p, ll> toClass;
    vp classes;
    ll cur = 0;
    for (ll i = 0; i < N; i++)
    {
        p c(bNormalized[i], cNormalized[i]);
        if (toClass.count(c) > 0) continue;
        toClass[c] = cur++;
        classes.pb(c);
    }
    ll classCnt = cur;
    v myClass(N);
    vv byClass(classCnt);
    for (ll i = 0; i < N; i++)
    {
        myClass[i] = toClass[p(bNormalized[i], cNormalized[i])];
        byClass[myClass[i]].pb(i);
    }
    vb reachable = getReachable(classes);
    vvv classExpectation(classCnt, vv(3));
    for (ll i = 0; i < N; i++)
    {
        classExpectation[myClass[i]][offset[i]].pb(i);
    }
    ll Q; cin >> Q;
    string scmp; cin >> scmp;
    v cmp(N);
    for (ll i = 0; i < N; i++) cmp[i] = conv[scmp[i]];
    vector<set<p>> ranges(3);
    ll last = 0;
    for (ll i = 1; i < N; i++)
    {
        if (cmp[i] != cmp[last])
        {
            ranges[cmp[last]].emplace(last, i - 1);
            last = i;
        }
    }
    ranges[cmp[last]].emplace(last, N - 1);
    vv notMatchingCnt(classCnt, v(3, 0));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < 3; j++)
        {
            if (j != (cmp[i] + offset[i]) % 3) notMatchingCnt[myClass[i]][j]++;
        }
    }
    bool isValid = checkValidity(notMatchingCnt, reachable);
    if (isValid) cout << "Yes\n";
    else cout << "No\n";
    while (Q--)
    {
        ll l, r;
        char asChar;
        cin >> l >> r >> asChar; l--; r--;
        ll val = conv[asChar];
        for (ll i = 0; i < 3; i++)
        {
            auto ptr = ranges[i].lower_bound(p(l, -INF));
            if (ptr != ranges[i].begin())
            {
                ptr--;
                if ((*ptr).s > r)
                {
                    substract(notMatchingCnt, getInvalid(l, r, classExpectation, i));
                    ll start=  (*ptr).f;
                    ll end = (*ptr).s;
                    ranges[i].erase(ptr);
                    ranges[i].emplace(start, l - 1);
                    ranges[i].emplace(r + 1, end);
                    continue;
                }
                else if ((*ptr).s >= l)
                {
                    substract(notMatchingCnt, getInvalid(l, (*ptr).s, classExpectation, i));
                    ll start = (*ptr).f;
                    ranges[i].erase(ptr);
                    ranges[i].emplace(start, l - 1);
                }
            }
            while (true)
            {
                auto ptr = ranges[i].lower_bound(p(l, -INF));
                if (ptr == ranges[i].end() || (*ptr).f > r) break;
                substract(notMatchingCnt, getInvalid((*ptr).f, min((*ptr).s, r), classExpectation, i));
                if ((*ptr).s > r)
                {
                    ll e = (*ptr).s;
                    ranges[i].erase(ptr);
                    ranges[i].emplace(r + 1, e);
                    break;
                }
                else
                {
                    ranges[i].erase(ptr);
                }
            }
        }
        ranges[val].emplace(l, r);
        add(notMatchingCnt, getInvalid(l, r, classExpectation, val));
        bool isValid = checkValidity(notMatchingCnt, reachable);
        if (isValid) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'vb getReachable(vp&)':
Main.cpp:71:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (ll i = 0; i < reachable.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void add(vv&, vv)':
Main.cpp:110:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (ll i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:112:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (ll j = 0; j < a[0].size(); j++)
      |                        ~~^~~~~~~~~~~~~
Main.cpp: In function 'void substract(vv&, vv)':
Main.cpp:121:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (ll i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:123:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (ll j = 0; j < a[0].size(); j++)
      |                        ~~^~~~~~~~~~~~~

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