제출 #911180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911180		lighton	무지개나라 (APIO17_rainbow)	C++17	100 / 100	810 ms	272956 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
using namespace std;
typedef long long ll;
int minr,maxr,minc,maxc;
struct Node{
    int v,l,r;
} def = {0,0,0};
struct ST{
    int row,col;
    vector<set<int> > S;
    vector<int> T;
    vector<int> root = {0};
    vector<Node> node = {def};
    void update(int now, int prv, int s, int e, int f, int x){
        if(s==e){node[now].v = node[prv].v+x; return;}
        int m = s+e>>1;
        if(f<=m){
            node[now].l = node.size(); node.push_back(def);
            node[now].r = node[prv].r;
            update(node[now].l,node[prv].l,s,m,f,x);
        }
        else{
            node[now].r = node.size(); node.push_back(def);
            node[now].l = node[prv].l;
            update(node[now].r,node[prv].r,m+1,e,f,x);
        }
        node[now].v = node[node[now].l].v + node[node[now].r].v;
    }
    int query(int now , int prv, int s, int e,int l ,int r){
        if(l<=s && e<=r) return node[now].v-node[prv].v;
        if(r<s || l>e) return 0;
        int m = s+e>>1;
        return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r);
    }

    void init(int R, int C){
        row = R+1;
        col = C+1;
        S.resize(row+1);
        T.resize(row+1);
    }
    void add(int R, int C){
        if(S[R].find(C) == S[R].end()) S[R].insert(C);
    }
    void process(){
        int now = 0;
        forf(i,1,row){
            for(int j : S[i]){
                now++;
                root.push_back(node.size());
                node.push_back(def);
                update(root[now],root[now-1],1,col,j,1);
            }
            T[i] = now;
        }
    }
    int query(int r1, int c1, int r2, int c2){
        int now = T[r2];
        int prv = T[r1-1];
        return query(root[now],root[prv],1,col,c1,c2);
    }
} F,V,Ex,Ey;

void mark(int row, int col){
    F.add(row,col);
    V.add(row,col); V.add(row+1,col); V.add(row,col+1); V.add(row+1,col+1);
    Ex.add(row,col);Ex.add(row+1,col);
    Ey.add(row,col); Ey.add(row,col+1);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    int r,c;
    r=R;c=C;
    F.init(r,c);V.init(r,c);Ex.init(r,c);Ey.init(r,c);

    int row = sr, col =sc;
    minr = row; maxr = row; minc = col; maxc = col;
    mark(row,col);
    forf(i,0,M-1){
        if(S[i] == 'N') row--;
        if(S[i] == 'S') row++;
        if(S[i] == 'E') col++;
        if(S[i] == 'W') col--;
        mark(row,col);
        minr = min(minr,row); maxr = max(maxr,row);
        minc = min(minc,col); maxc = max(maxc,col);
    }

    F.process();V.process();Ex.process();Ey.process();
}

int colour(int ar, int ac, int br, int bc) {
    int f = F.query(ar,ac,br,bc);
    int v = V.query(ar+1,ac+1,br,bc);
    int ex = Ex.query(ar+1,ac,br,bc);
    int ey = Ey.query(ar,ac+1,br,bc);
    int p = 0;
    if(ar<minr && br>maxr && ac<minc && bc>maxc) p = 1;
    return 1-v+ex+ey-f+p;
}

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
rainbow.cpp:18:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int m = s+e>>1;
      |                 ~^~
rainbow.cpp: In member function 'int ST::query(int, int, int, int, int, int)':
rainbow.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = s+e>>1;
      |                 ~^~

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26