Submission #1095370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095370		cpptowin	Crossing (JOI21_crossing)	C++17	100 / 100	298 ms	160928 KiB

Main

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
const int base = 31;
int n, q;
map<int, bool> mp;
vi a[3];
int p[maxn];
void backtrack(vi v)
{
    int hsh = 0;
    fo(i, 0, n - 1) hsh = (hsh * base + v[i]) % mod;
    if (mp.count(hsh))
        return;
    mp[hsh] = 1;
    fo(j, 0, 2)
    {
        vi cur(n);
        fo(i, 0, n - 1)
        {
            if(v[i] != a[j][i])
            cur[i] = 3 - v[i] - a[j][i];
            else cur[i] = v[i];
        }
        backtrack(cur);
    }
}
struct node
{
    int h, len;
    node()
    {
        h = len = 0;
    }
    node operator+(const node b)
    {
        if(len == 0) return b;
        if(b.len == 0) return *this;
        node ans;
        ans.len = len + b.len;
        ans.h = (h * p[b.len] + b.h) % mod;
        return ans;
    }
} st[4 * maxn];
int lazy[4 * maxn];
int hh[maxn][3];
void down(int id, int l, int r)
{
    if (lazy[id] == -1)
        return;
    int mid = l + r >> 1;
    st[id << 1].h = hh[mid - l + 1][lazy[id]];
    st[id << 1 | 1].h = hh[r - mid][lazy[id]];
    lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
    lazy[id] = -1;
}
void update(int id, int l, int r, int u, int v, int val)
{
    if (u > r || l > v)
        return;
    if (u <= l && r <= v)
    {
        st[id].h = hh[r - l + 1][val];
        st[id].len = r - l + 1;
        lazy[id] = val;
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

node get(int id, int l, int r, int u, int v)
{
    if (l > v || u > r)
        return node();
    if (u <= l && r <= v)
        return st[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(lazy, -1, sizeof lazy);
    cin >> n;
    p[0] = 1;
    fo(i, 1, maxn - 1)
    {
        p[i] = p[i - 1] * base % mod;
        fo(j, 0, 2)
        {
            hh[i][j] = (hh[i - 1][j] * base + j) % mod;
        }
    }
    fo(i, 0, 2) a[i].resize(n);
    fo(i, 0, 2) for (int &it : a[i])
    {
        char t;
        cin >> t;
        if (t == 'J')
            it = 0;
        else if (t == 'O')
            it = 1;
        else if (t == 'I')
            it = 2;
    }
    fo(i, 0, 2)
    {
        backtrack(a[i]);
    }
    cin >> q;
    fo(i, 1, n)
    {
        int it;
        char t;
        cin >> t;
        if (t == 'J')
            it = 0;
        else if (t == 'O')
            it = 1;
        else if (t == 'I')
            it = 2;
        update(1, 1, n, i, i, it);
    }
    if(mp.count(st[1].h)) cout << "Yes";
    else cout << "No";
    en;
    while (q--)
    {
        int it;
        char t;
        int l, r;
        cin >> l >> r >> t;
        if (t == 'J')
            it = 0;
        else if (t == 'O')
            it = 1;
        else if (t == 'I')
            it = 2;
        update(1, 1, n, l, r, it);
        if(mp.count(st[1].h)) cout << "Yes";
        else cout << "No";
        en;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void down(long long int, long long int, long long int)':
Main.cpp:106:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: At global scope:
Main.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  140 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:206:15: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
  206 |         update(1, 1, n, l, r, it);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:189:15: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
  189 |         update(1, 1, n, i, i, it);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~

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