Submission #261760

#	Time	Username	Problem	Language	Result	Execution time	Memory
261760		tqbfjotld	Colors (RMI18_colors)	C++14	47 / 100	443 ms	46456 KiB

colors

#include <bits/stdc++.h>
using namespace std;

int init[150005];
int fin[150005];
vector<int> adjl[150005];
vector<pair<int,int> > order;
queue<pair<int,int> > q;
bool visited[150005];
int counter = 0;
int n,m;

void dfs2(int node){
    counter++;
    assert(counter<=n);
    for (auto x : adjl[node]){
        if (init[x]<=init[node] || fin[x]>init[node]){
            continue;
        }
        init[x] = init[node];
        dfs2(x);
    }
}
int counter2 = 0;

struct node{
    int s,e,v;
    int lazy;
    bool flag;
    node *l,*r;
    node (int _s, int _e){
        s = _s;
        e = _e;
        v = 0;
        flag = false;
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    void proc(){
        if (!flag) return;
        v = lazy;
        if (s!=e){
            l->flag = true;
            r->flag = true;
            l->lazy = lazy;
            r->lazy = lazy;
        }
        flag = false;
    }
    void upd(int a,int b, int val){
        //printf("upd %d %d %d to %d %d\n",a,b,val,s,e);
        proc();
        if (a<=s && e<=b) {
            lazy = val;
            flag = true;
            return;
        }
        if (b<=(s+e)/2){
            l->upd(a,b,val);
        }
        else if (a>(s+e)/2){
            r->upd(a,b,val);
        }
        else {
            l->upd(a,b,val);
            r->upd(a,b,val);
        }
        l->proc();r->proc();
        v = min(l->v,r->v);
    }
    int qu(int a, int b){
        //printf("qu %d %d to %d %d\n",a,b,s,e);
        proc();
        if (a<=s && e<=b) {
            return v;
        }
        else if (b<=(s+e)/2){
            return l->qu(a,b);
        }
        else if (a>(s+e)/2){
            return r->qu(a,b);
        }
        else return min(l->qu(a,b),r->qu(a,b));
    }
}*ro1,*ro2;

int main(){
int test;
scanf("%d",&test);
while (test--){
    scanf("%d%d",&n,&m);
    counter2 += n*n;
    //assert(counter2<=5000000);
    for (int x = 1; x<=n; x++){
        scanf("%d",&init[x]);
        adjl[x].clear();
    }
    bool poss1 = true;
    order.clear();
    for (int x = 1; x<=n; x++){
        scanf("%d",&fin[x]);
        if (fin[x]>init[x]) poss1 = false;
        order.push_back({init[x],x});
    }
    sort(order.begin(),order.end(),greater<pair<int,int> >());
    for (int x = 0; x<m; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }
    if (!poss1) {
        printf("0\n");
        continue;
    }
    bool poss = true;
    /*for (auto x : order){
        for (int x = 1; x<=n; x++) visited[x] = false;
        if (!dfs(x.second,fin[x.second],fin[x.second])){
            printf("0\n");
            poss = false;
            break;
        }
    }*/
    if (counter2<=5000000 && true){
        for (auto x : order){
            counter = 0;
            dfs2(x.second);
        }
        for (int x = 1; x<=n; x++){
            if (init[x]!=fin[x]){
                poss = false;
                printf("0\n");
                break;
            }
        }
        if (poss){
            printf("1\n");
        }
    }
    else{
        ro1 = new node(0,n+1);
        ro2 = new node(0,n+1);
        for (int x = 1; x<=n; x++){
            ro1->upd(x,x,init[x]);
            ro2->upd(x,x,-fin[x]);
        }
        for (auto x : order){
            init[x.second] = ro1->qu(x.second,x.second);
            int r1 = x.second;
            int r2 = n+1;
            while (r1+1<r2){
                int md = (r1+r2)/2;
                if (ro1->qu(x.second,md)<init[x.second] || ro2->qu(x.second,md)<-init[x.second]){
                    r2 = md;
                }
                else r1 = md;
            }
            int l1 = 0;
            int l2 = x.second;
            while (l1+1<l2){
                int md = (l1+l2)/2;
                if (ro1->qu(md,x.second)<init[x.second] || ro2->qu(md,x.second)<-init[x.second]){
                    l1 = md;
                }
                else l2 = md;
            }
            ro1->upd(l2,r1,init[x.second]);
        }
        for (int x = 1; x<=n; x++){
            init[x] = ro1->qu(x,x);
            //printf("final cols %d = %d\n",x,init[x]);
        }
        for (int x = 1; x<=n; x++){
            if (init[x]!=fin[x]){
                poss = false;
                printf("0\n");
                break;
            }
        }
        if (poss){
            printf("1\n");
        }
    }
}
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:91:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d",&test);
 ~~~~~^~~~~~~~~~~~
colors.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
colors.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&init[x]);
         ~~~~~^~~~~~~~~~~~~~~
colors.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&fin[x]);
         ~~~~~^~~~~~~~~~~~~~
colors.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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