oj.uz

Submission #403016

# Submission time Handle Problem Language Result Execution time Memory
403016 2021-05-12T16:27:05 Z teehandsome Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 234 ms 16452 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

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

const int mxn=2e5+10;
bool flag[2][mxn];
int dm[4]={-1,0,1,0};
int dn[4]={0,1,0,-1};
char dir[4]={'N','E','S','W'};

struct dt {
    int cnt; bool ul,dl,ur,dr;
};

dt t[3][3*mxn];

dt unite(dt l,dt r) {
    dt res;
    res.cnt=l.cnt+r.cnt;
    res.ul=l.ul; res.dl=l.dl;
    res.ur=r.ur; res.dr=r.dr;
    if(l.cnt and r.cnt) {
        if((!l.ur and !r.ul) or (!l.dr and !r.dl)) res.cnt--;
    }
    return res;
}

void build(int v,int tl,int tr) {
    if(tl>tr) return;
    if(tl==tr) {
        if(flag[0][tl] and flag[1][tl]) {
            t[2][v]={0,true,true,true,true};
        }
        else {
            t[2][v]={1,flag[0][tl],flag[1][tl],flag[0][tl],flag[1][tl]};
        }
        return;
    }
    int mid=(tl+tr)/2;
    build(2*v,tl,mid);  build(2*v+1,mid+1,tr);
    t[2][v]=unite(t[2][2*v],t[2][2*v+1]);
}
void debugdt(dt x) {
    cout<<"#"<<": "<<x.cnt<<endl;
}
dt query(int idx,int v,int tl,int tr,int l,int r) {
    if(tl>tr or tl>r or tr<l) return {0,1,1,1,1};
    if(tl>=l and tr<=r) return t[idx][v];
    int mid=(tl+tr)/2;
    dt L=query(idx,2*v,tl,mid,l,r);
    dt R=query(idx,2*v+1,mid+1,tr,l,r);
    dt res=unite(L,R);
//    debug(L.cnt,R.cnt,res.cnt);
    return unite(L,R);
}

int r,c;

void build2(int idx,int v,int tl,int tr) {
    if(tl>tr) return;
    if(tl==tr) {
        if(flag[idx][tl]) t[idx][v]={0,1,1,1,1};
        else t[idx][v]={1,0,0,0,0};
    }
    else {
        int mid=(tl+tr)/2;
        build2(idx,2*v,tl,mid);
        build2(idx,2*v+1,mid+1,tr);
        t[idx][v]=unite(t[idx][2*v],t[idx][2*v+1]);
    }
}

void deebug(int idx,int v,int tl,int tr) {
    if(tl>tr) return;
    cout<<"# {"<<tl<<" "<<tr<<"}"<<": "<<t[idx][v].cnt<<endl;
    if(tl==tr) return;
    int mid=(tl+tr)/2;
    deebug(idx,2*v,tl,mid);
    deebug(idx,2*v+1,mid+1,tr);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    r=R,c=C;
    --sr; --sc;
    flag[sr][sc]=true;
    for(int i=0;i<M;i++) {
        for(int j=0;j<4;j++) {
            if(S[i]==dir[j]) {
                sr+=dm[j]; sc+=dn[j]; break;
            }
        }
        flag[sr][sc]=true;
    }
//    for(int i=0;i<R;i++) {
//        for(int j=0;j<C;j++) {
//            cout<<flag[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    build(1,0,C-1);
    for(int i=0;i<2;i++) {
        build2(i,1,0,C-1);
    }
//    deebug(1,1,0,c-1);

}


int colour(int ar, int ac, int br, int bc) {
    dt ans;
    --ar; --ac; --br; --bc;
    if(ar==br) {
        ans=query(ar,1,0,c-1,ac,bc);
    }
    else {
        ans=query(2,1,0,c-1,ac,bc);
    }
    return ans.cnt;
}

Compilation message

rainbow.cpp: In function 'dt query(int, int, int, int, int, int)':
rainbow.cpp:80:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   80 |     dt res=unite(L,R);
      |        ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 192 ms 16196 KB Output is correct
4 Correct 188 ms 16452 KB Output is correct
5 Correct 191 ms 16452 KB Output is correct
6 Correct 188 ms 16324 KB Output is correct
7 Correct 176 ms 16396 KB Output is correct
8 Correct 187 ms 16176 KB Output is correct
9 Correct 187 ms 16376 KB Output is correct
10 Correct 234 ms 16384 KB Output is correct
11 Correct 184 ms 16256 KB Output is correct
12 Correct 76 ms 16324 KB Output is correct
13 Correct 72 ms 16360 KB Output is correct
14 Correct 74 ms 16388 KB Output is correct
15 Correct 71 ms 16348 KB Output is correct
16 Correct 189 ms 16372 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 2 ms 716 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -