Submission #1300214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300214		minhquaanz	Crossing (JOI21_crossing)	C++20	26 / 100	234 ms	17872 KiB

Main

/*Code by TMQ*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define em emplace
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FIV(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define all(x) (x).begin(), (x).end()
#define reset(a, x) (memset(a, x, sizeof(a)));
#define Unique(v) v.erase(unique(all(v)), v.end());
#define testcase \
    int tc;      \
    cin >> tc;   \
    while (tc--) \
        solve();
#define howlong cerr << "Time elapsed: " << fixed << setprecision(9) << (double)clock() / CLOCKS_PER_SEC << "s";
#define what_is(x) cerr << #x << " is " << x << '\n';
ll inline GCD(ll a, ll b) { return !b ? abs(a) : GCD(b, a % b); }
ll inline LCM(ll a, ll b) { return (a / GCD(a, b) * b); }
template <class X, class Y>
bool maximize(X &x, Y y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
    return false;
};
template <class X, class Y>
bool minimize(X &x, Y y)
{
    if (x > y)
    {
        x = y;
        return true;
    }
    return false;
};
///=====================================s========================================
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask  (1 << (i))))
///============================================================================
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)                   \
    {                                 \
        cerr << "[" << #x << "] = ["; \
        _print(x);                    \
    }
#else
#define debug(x...)
#endif
///============================================================================
void TASK(string task)
{
    if (fopen((task + ".inp").c_str(), "r"))
    {
        freopen((task + ".inp").c_str(), "r", stdin);
        freopen((task + ".out").c_str(), "w", stdout);
    }
}
///============================================================================
const ll mod = 1e9 + 7;
const ll inf = (ll)1e18 + 10;
const ll nmax = 2e5 + 5;
///============================================================================
int n;
string S1, S2, S3;
string T;
int q, L[nmax], R[nmax];
char C[nmax];
char nxt[100][100], ch[] = {'J', 'O', 'I'};
const ll base = 137;
namespace sub12{
    vector<ll> spw;
    vector<ll> sum, lazy;
    ll cal(int l, int r)
    {
        return ((spw[r] - spw[l - 1]) % mod + mod) % mod;
    }
    void push(int k, int l, int r, ll lz)
    {
        sum[k] = lz * cal(l, r) % mod;
        lazy[k] = lz;
        ///debug(k, l, r, lz);
    }
    void down(int k, int l, int r)
    {
        if(lazy[k] > 0)
        {
            int mid = l + r >> 1;
            push(k * 2, l, mid, lazy[k]);
            push(k * 2 + 1, mid + 1, r, lazy[k]);
            lazy[k] = 0;
        }
    }
    void update(int l, int r, int u, int v, ll val, int k = 1)
    {
        ///debug(l, r, u, v, val, k);
        if (l > v || r < u)
            return;
        if (u <= l && r <= v)
        {
            push(k, l, r, val);
            return;
        }
        down(k, l, r);
        int mid = (l + r) >> 1;
        update(l, mid, u, v, val, k * 2);
        update(mid + 1, r, u, v, val, k * 2 + 1);
        sum[k] = (sum[k * 2] + sum[k * 2 + 1]) % mod;
    }
    ll get(int l, int r, int u, int v, int k = 1)
    {
        if (l > v || r < u)
            return 0;
        if (u <= l && r <= v)
            return sum[k];
        int mid = (l + r) >> 1;
        down(k, l, r);
        ll getL = get(l, mid, u, v, k * 2);
        ll getR = get(mid + 1, r, u, v, k * 2 + 1);
        return (getL + getR) % mod;
    }
    void solve()
    {
        spw.resize(n + 1);
        sum.resize(4 * n + 5);
        lazy.resize(4 * n + 5);
        ll pw = 1, hs = 0;
        T = ' ' + T;
        S1 = ' ' + S1;
        for(int i = 1; i <= n; i++)
        {
            pw = pw * base % mod;
            spw[i] = (spw[i - 1] + pw) % mod;
            ///cout << spw[i] << ' ' << pw << '\n';
            hs = (hs + pw * (S1[i] - 'A' + 1) % mod) % mod;
        }
        ///cout << hs << '\n';
        if(T == S1)
            cout << "Yes" << '\n';
        else
            cout << "No" << '\n';
        for(int i = 1; i <= n; i++)
            update(1, n, i, i, T[i] - 'A' + 1);
        ///cout << get(1, n, 1, n) << '\n';
        for(int qi = 1; qi <= q; qi++)
        {
            int l = L[qi], r = R[qi];
            char c = C[qi];
            update(1, n, l, r, c - 'A' + 1);
            ll s = get(1, n, 1, n);
            if(s == hs)
                cout << "Yes" << '\n';
            else
                cout << "No" << '\n';
        }
    }
}
///============================================================================
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    TASK("ENCHANTING");
    cin >> n;
    cin >> S1 >> S2 >> S3;
    cin >> q;
    cin >> T;
    for(int i = 1; i <= q; i++)
    {
        cin >> L[i] >> R[i] >> C[i];
    }
    for(int i = 0; i < 3; i++)
    {
        char c = ch[i];
        nxt[c][c] = c;
        for(int j = i + 1; j < 3; j++)
        {
            int id = 3 - (i + j);
            nxt[ch[i]][ch[j]] = nxt[ch[j]][ch[i]] = ch[id];
        }
    }
//    for(int i = 0; i < 3; i++)
//        for(int j = 0; j < 3; j++)
//        cout << ch[i] << ' ' << ch[j] << ' ' << nxt[ch[i]][ch[j]] << '\n';
    if(S1 == S2 && S2 == S3)
    {
        sub12::solve();
        return 0;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void TASK(std::string)':
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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