oj.uz

답안 #202123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202123 2020-02-14T00:57:14 Z knon0501 무지개나라 (APIO17_rainbow) C++14
0 / 100
 143 ms 129256 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;

int nn;
int r,c;
int vcnt,ecnt;
vector<int> seg[3][MX*4]; ///정점,세로,가로
 ///가로선분

int f(int lef,int rig,int x,int y,int z,int w,int k,int lev){
    if(x>y || lef>y ||x>rig)return 0;
    if(lef>=x && rig<=y){
        return upper_bound(seg[k][lev].begin(),seg[k][lev].end(),w)-upper_bound(seg[k][lev].begin(),seg[k][lev].end(),z);
    }
    int mid=(lef+rig)/2;
    return f(lef,mid,x,y,z,w,k,lev*2)+f(mid+1,rig,x,y,z,w,k,lev*2+1);
}
void upd(int x,int y){
    seg[0][nn+x-1].push_back(y);
}

void upd2(int x,int y){ ///세로 선분
    seg[1][nn+x-1].push_back(y);
}
void upd3(int x,int y){///가로선분
    seg[2][nn+x-1].push_back(y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    nn=254288;
    r=R+2;
    c=C+2;

    int i;
    int y=sr;
    int x=sc;

    for(i=0 ; i<M ; i++){
        if(S[i]=='E'){
            x++;
            upd(x+1,y);
            upd(x+1,y+1);
            upd2(x+1,y);
            upd3(y,x);
            upd3(y+1,x);
        }
        if(S[i]=='W'){
            x--;
            upd(x,y);
            upd(x,y+1);
            upd2(x,y);
            upd3(y,x);
            upd3(y+1,x);
        }
        if(S[i]=='S'){
            y++;
            upd(x,y+1);
            upd(x+1,y+1);
            upd2(x,y);
            upd2(x+1,y);
            upd3(y+1,x);
        }
        if(S[i]=='N'){
            y--;
            upd(x,y);
            upd(x+1,y);
            upd2(x,y);
            upd2(x+1,y);
            upd3(y,x);
        }

    }
    for(i=1 ; i<=c ; i++){
        unique(seg[0][nn+i-1].begin(),seg[0][nn+i-1].end());
        sort(seg[0][nn+i-1].begin(),seg[0][nn+i-1].end());
        unique(seg[1][nn+i-1].begin(),seg[1][nn+i-1].end());
        sort(seg[1][nn+i-1].begin(),seg[1][nn+i-1].end());
        unique(seg[2][nn+i-1].begin(),seg[2][nn+i-1].end());
        sort(seg[2][nn+i-1].begin(),seg[2][nn+i-1].end());
    }
    for(i=nn-1 ; i>=1 ; i--){
        merge(seg[0][i*2].begin(),seg[0][i*2].end(),seg[0][i*2+1].begin(),seg[0][i*2+1].end(),seg[0][i].begin());
        merge(seg[1][i*2].begin(),seg[1][i*2].end(),seg[1][i*2+1].begin(),seg[1][i*2+1].end(),seg[1][i].begin());
        merge(seg[2][i*2].begin(),seg[2][i*2].end(),seg[2][i*2+1].begin(),seg[2][i*2+1].end(),seg[2][i].begin());
    }
}

int colour(int ar, int ac, int br, int bc) {
    int A=f(1,nn,ac+1,bc,ar,br,1,1);
    int B=f(1,nn,ac,bc,ar+1,br,2,1);
    int C=f(1,nn,ac+1,bc,ar,ar,0,1)+f(1,nn,ac+1,bc,br+1,br+1,0,1);
    int D=f(1,nn,ac,ac,ar+1,br,0,1)+f(1,nn,bc,bc,ar+1,br,0,1);
    int E=f(1,nn,ac,ac,ar,ar,0,1)+f(1,nn,ac,ac,br,br,0,1)+f(1,nn,bc,bc,ar,ar,0,1)+f(1,nn,bc,bc,br,br,0,1);
    int F=f(1,nn,ac+1,bc,ar+1,br,0,1);
    int G=f(1,nn,ac,bc,ar,br,0,1);
    int v=C+D+F+4-E;
    int e=A+B+C+2+D+2;
    return e-v-G;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 104 ms 114680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 114816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 56696 KB Output is correct
2 Runtime error 143 ms 129256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 104 ms 114680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 104 ms 114680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -