Submission #1259227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259227		SalihSahin	Colors (RMI18_colors)	C++20	0 / 100	3094 ms	7488 KiB

colors

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int LIM = 150001;
vi edges[LIM];
vi a(LIM),b(LIM),par(LIM);
 
int dfs(int node,int p,const int x) {
    if (a[node] == x) return node;
    for (auto it : edges[node]) {
        if (it == p) continue;
        if (a[it] < x) continue;
        par[it] = node;
        int y = dfs(it,node,x);
        if (y) return y;
    }
    return 0;
}
 
 
struct ST {
    vi t,lazy;
 
    ST(int nn) {
        t.assign(4*nn+1,1e9+1);
        lazy.assign(4*nn+1,1e9+2);
    }
 
 
    void push(int node,bool leaf) {
        t[node] = min(t[node],lazy[node]);
        if (!leaf) {
            lazy[2*node] = lazy[node];
            lazy[2*node+1] = lazy[node];
        }
        lazy[node] = 1e9+2;
    }
 
 
    int query(int node,int l,int r,int L,int R) {
        push(node,l==r);
        if (l > R || r < L) return 1e9+1;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return min(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }
 
    void update(int node,int l,int r,int L,int R,int v) {
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lazy[node] = v;
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
        t[node] = min(t[2*node],t[2*node+1]);
    }
};
 
 
void solve() {
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) edges[i].clear();
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) cin >> b[i];
    set<int> pos[n+1];
    for (int i=1;i<=n;i++) pos[b[i]].insert(i);
    for (int i=1;i<=m;i++) {
        int x,y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for (int i=1;i<=n;i++) {
        if (a[i] < b[i]) {
            cout << 0 << '\n';
            return;
        }
    }
    ST st(n);
    for (int i=1;i<=n;i++) st.update(1,1,n,i,i,a[i]); 
    vi lst;
    while (1) {
        int mx = 0;
        int select = 0;
        for (int i=1;i<=n;i++) {
            if (st.query(1,1,n,i,i) != b[i] && b[i] > mx) {
                mx = b[i];
                select = i;
            }
        }
        if (!select) {
            cout << 1 << '\n';
            return;
        }
        auto iter = pos[b[select]].upper_bound(select);
        if (iter != pos[b[select]].end()) {
            int nxt = *iter;
            if (st.query(1,1,n,nxt,nxt) == mx && st.query(1,1,n,select,nxt) >= mx) {
                st.update(1,1,n,select,nxt,mx);
            }
        }
        else if (iter != pos[b[select]].begin()) {
            int prv = *(--iter);
            if (st.query(1,1,n,prv,prv) == mx && st.query(1,1,n,prv,select) >= mx) {
                st.update(1,1,n,prv,select,mx);
            }
        }
        else {
            cout << 0 << '\n';
            return;
        }
    }
} 
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22