oj.uz

답안 #733426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733426 2023-04-30T17:09:49 Z 1075508020060209tc 무지개나라 (APIO17_rainbow) C++14
0 / 100
 2 ms 596 KB 
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
int n;int m;int sx;int sy;
string s;
int gr[5][200005];

struct SGTR{
int l;int r;
int gp[3];
}tr[800005];

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].gp[0]=0;
    tr[nw].gp[1]=0;
    tr[nw].gp[2]=0;
    if(gr[1][l]||gr[2][l]){
        tr[nw].gp[0]=1;
    }
    if(gr[1][l]){
        tr[nw].gp[1]=1;
    }
    if(gr[2][l]){
        tr[nw].gp[2]=1;
    }
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
tr[nw].gp[0]=tr[nw*2].gp[0]+tr[nw*2+1].gp[0];
if((gr[1][mi]&&gr[1][mi+1])||(gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[0]--;
}
if((gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[2]--;
}
if((gr[1][mi]&&gr[1][mi+1])){
    tr[nw].gp[1]--;
}
}



void init(int R, int C, int sr, int sc, int M, char *S) {
n=R;m=C;
gr[sr][sc]=1;
for(int i=0;i<M;i++){
    if(S[i]=='N'){sr--;}
    if(S[i]=='S'){sr++;}
    if(S[i]=='W'){sc--;}
    if(S[i]=='E'){sc++;}
    gr[sr][sc]=1;
}
for(int i=1;i<=C;i++){
    gr[1][i]^=1;
    gr[2][i]^=1;
}
buildtr(1,1,C);
}

int ans;int vs;

void slv(int pl,int id){
if(id==0){
    if( (gr[1][pl-1]&&gr[1][pl])||(gr[2][pl-1]&&gr[2][pl])  ){
        ans--;
    }
    return;
}
    if( (gr[id][pl-1]&&gr[id][pl])  ){
        ans--;
    }

}

void qry(int nw,int l,int r,int id){
if(tr[nw].l>=l&&tr[nw].r<=r){
    ans+=tr[nw].gp[id];
    if(vs){slv(tr[nw].l,id);}
    vs=1;
    return;
}
if(tr[nw].l>r||tr[nw].r<l){
    return;
}
qry(nw*2,l,r,id);qry(nw*2+1,l,r,id);
}



int colour(int ar, int ac, int br, int bc) {
ans=0;vs=0;
if(ar==1&&br==2){
    qry(1,ac,bc,0);
    return ans;
}
qry(1,ac,bc,ar);
return ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -