oj.uz

답안 #1054037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054037 2024-08-12T05:11:42 Z 변재우(#11060) 무지개나라 (APIO17_rainbow) C++14
0 / 100
 37 ms 13044 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int Nmax=1010, S=1<<10;
int A[Nmax][Nmax], B[Nmax][Nmax];

class Seg {
public:
    void Update(int k) {Update(1, 1, S, k);}
    int Query(int l, int r) {return Query(1, 1, S, l, r).v;}
private:
    struct Data {
        int v, l, r;
    }Tree[2*S];
    Data Merge(Data a, Data b) {
        return {a.v+b.v-(a.r&b.l), a.l, b.r};
    }
    void Update(int node, int s, int e, int k) {
        if(s==e) {
            Tree[node]={1, 1, 1};
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k);
        else Update(rch, m+1, e, k);
        Tree[node]=Merge(Tree[lch], Tree[rch]);
    }
    Data Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return {0, 0, 0};
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return Merge(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
    }
}X[Nmax], Y[Nmax];

void init(int R, int C, int sr, int sc, int M, char *S) {
    A[sr][sc]=true;
    for(int i=0; i<strlen(S); i++) {
        if(S[i]=='W') sc--;
        else if(S[i]=='E') sc++;
        else if(S[i]=='N') sr--;
        else sr++;
        A[sr][sc]=true;
    }
    for(int i=1; i<=R; i++) for(int j=1; j<=C; j++) if(A[i][j]) X[i].Update(j), Y[j].Update(i);
    for(int i=1; i<=R; i++) for(int j=1; j<=C; j++)
        B[i][j]=B[i][j-1]+B[i-1][j]-B[i-1][j-1]+A[i][j];
}

bool All(int r1, int c1, int r2, int c2) {
    return (B[r2][c2]-B[r1-1][c2]-B[r2][c1-1]+B[r1-1][c1-1]==(r2-r1+1)*(c2-c1+1));
}

int colour(int ar, int ac, int br, int bc) {
    for(int s=ar, e=br; s<=e; ) {
        int m=(s+e)/2;
        if(All(ar, ac, m, bc)) ar=m+1, s=m+1;
        else e=m-1;
    }
    for(int s=ar, e=ac; s<=e; ) {
        int m=(s+e)/2;
        if(All(m, ac, br, bc)) br=m-1, e=m-1;
        else s=m+1;
    }
    if(ar>br) return 0;
    for(int s=ac, e=bc; s<=e; ) {
        int m=(s+e)/2;
        if(All(ar, ac, br, m)) ac=m+1, s=m+1;
        else e=m-1;
    }
    for(int s=ac, e=bc; s<=e; ) {
        int m=(s+e)/2;
        if(All(ar, m, br, bc)) bc=m-1, e=m-1;
        else s=m+1;
    }
    if(ac>bc) return 0;
    return max(1, X[ar].Query(ac, bc)+X[br].Query(ac, bc)+Y[ac].Query(ar, br)+Y[bc].Query(ar, br)-A[ar][ac]-A[ar][bc]-A[br][ac]-A[br][bc]);
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0; i<strlen(S); i++) {
      |                  ~^~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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