Submission #429050

#	Time	Username	Problem	Language	Result	Execution time	Memory
429050		muhammad_hokimiyon	Crossing (JOI21_crossing)	C++14	100 / 100	1834 ms	123712 KiB

Main

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int N = 2e5 + 7;
const long long mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int A[N];
vector<vector<int>> col;

struct seg{
        int t[4 * N][3];

        void build(int x, int l, int r)
        {
                if(l == r){
                        t[x][A[l]] = 1;
                        return;
                }
                int m = (l + r) / 2;
                build(x + x, l, m);
                build(x + x + 1, m + 1, r);
                for(int i = 0; i < 3; i++){
                        t[x][i] = t[x + x][i] + t[x + x + 1][i];
                }
        }
} D[10];

int used[4 * N][20];

void go(int x)
{
        for(int i = 0; i < (int)col.size(); i++){
                used[x][i] = (used[x + x][i] & used[x + x + 1][i]);
        }
}

void go(int x, int l, int r, int val)
{
        for(int i = 0; i < (int)col.size(); i++){
                if(D[i].t[x][val] == r - l + 1)used[x][i] = 1;
                else used[x][i] = 0;
        }
}

void build(int x, int l, int r)
{
        if(l == r){
                go(x, l, r, A[l]);
                return;
        }
        int m = (l + r) / 2;
        build(x + x, l, m);
        build(x + x + 1, m + 1, r);
        go(x);
}

int lz[4 * N];

void push(int x, int l, int r)
{
        int m = (l + r) / 2;
        if(lz[x] != -1){
                lz[x + x] = lz[x + x + 1] = lz[x];
                go(x + x, l, m, lz[x]);
                go(x + x + 1, m + 1, r, lz[x]);
                lz[x] = -1;
        }
}

void upd(int x, int l, int r, int tl, int tr, int val)
{
        if(tl > tr)return;
        if(l == tl && r == tr){
                go(x, l, r, val);
                lz[x] = val;
                return;
        }
        int m = (l + r) / 2;
        push(x, l, r);
        upd(x + x, l, m, tl, min(tr, m), val);
        upd(x + x + 1, m + 1, r, max(tl, m + 1), tr, val);
        go(x);
}

vector<int> get(string s)
{
        vector<int> res;
        for(int i = 0; i < n; i++){
                if(s[i] == 'I')res.push_back(0);
                else if(s[i] == 'J')res.push_back(1);
                else res.push_back(2);
        }
        return res;
}

bool f()
{
        for(int i = 0; i < (int)col.size(); i++){
                if(used[1][i])return true;
        }
        return false;
}

void solve()
{
        cin >> n;
        vector<int> a(n),b(n),c(n);
        set<vector<int>> s;
        string st;
        cin >> st;
        a = get(st);
        cin >> st;
        b = get(st);
        cin >> st;
        c = get(st);
        s.insert(a);
        s.insert(b);
        s.insert(c);
        while(true){
                bool f = false;
                vector<int> id;
                for(auto x : s){
                        for(auto y : s){
                               if(f)break;
                               vector<int> v;
                               for(int i = 0; i < n; i++){
                                        if(x[i] == y[i]){
                                                v.push_back(x[i]);
                                        }else v.push_back(3 - x[i] - y[i]);
                               }
                               if(s.find(v) == s.end()){
                                        id = v;
                                        f = true;
                               }
                        }
                }
                if(!f)break;
                s.insert(id);
        }
        assert((int)s.size() <= 10);
        for(auto x : s){
                col.push_back(x);
        }
        int G = 0;
        for(auto x : col){
                for(int i = 0; i < n; i++){
                        A[i + 1] = x[i];
                }
                D[G].build(1, 1, n);
                G++;
        }
        for(int i = 0; i < 4 * N; i++)lz[i] = -1;
        int q;
        cin >> q;
        cin >> st;
        auto x = get(st);
        for(int i = 0; i < n; i++){
                A[i + 1] = x[i];
        }
        build(1, 1, n);
        if(f())cout << "Yes\n";
        else cout << "No\n";
        while(q--){
                int l,r;
                char g;
                cin >> l >> r >> g;
                int id = -1;
                if(g == 'I')id = 0;
                else if(g == 'J')id = 1;
                else id = 2;
                upd(1, 1, n, l, r, id);
                if(f())cout << "Yes\n";
                else cout << "No\n";
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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