제출 #593974

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

rainbow

#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;

int r, c, sx, sy, m;
string s;
int lx, ly, rx, ry;
vector<pair<int,int>> g, ex, ey, two;



struct wavelet{
    int n;
    vector<vector<int>> vec, cnt;
    vector<int> X, Y;

    wavelet(){
    }

    void init(vector<pair<int,int>> v){
        n=v.size();
        vec.resize(4*n);
        cnt.resize(4*n);
        for(auto p:v) X.push_back(p.first), Y.push_back(p.second);
        sort(X.begin(), X.end()); 
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());
        sort(v.begin(), v.end());
        for(auto p:v){
            vec[0].push_back(lower_bound(Y.begin(), Y.end(), p.second)-Y.begin());
        }
        build(0, 0, Y.size());
    }

    void build(int x, int l, int r){
        if(r<=l+1) return;
        int m=(l+r)/2;
        cnt[x].resize(vec[x].size());
        for(int i=0; i<vec[x].size(); i++){
            cnt[x][i]=(i?cnt[x][i-1]:0)+(vec[x][i]<m);
            vec[2*x+1+(vec[x][i]>=m)].push_back(vec[x][i]);
        }
        build(2*x+1, l, m);
        build(2*x+2, m, r);
    }

    int query(int x, int l, int r, int li, int ri, int a, int b){ // ind [l,r] vals [a,b)
        if(l>=a && r<=b) return ri-li+1;
        if(l>=b || r<=a || ri<li) return 0;
        int m=(l+r)/2;
        int left_li=cnt[x][li]-(vec[x][li]<m);
        int left_ri=cnt[x][ri]-1;
        int right_li=li-cnt[x][li]+(vec[x][li]<m);
        int right_ri=ri-cnt[x][ri];
        return query(2*x+1, l, m, left_li, left_ri, a, b) + query(2*x+2, m, r, right_li, right_ri, a, b);
    }

    int rect(int a, int c, int b, int d){
        if(b<a || d<c) return 0;
        a=lower_bound(X.begin(), X.end(), a)-X.begin();
        b=upper_bound(X.begin(), X.end(), b)-X.begin()-1;
        c=lower_bound(Y.begin(), Y.end(), c)-Y.begin();
        d=upper_bound(Y.begin(), Y.end(), d)-Y.begin();
        return query(0, 0, Y.size(), a, b, c, d);
    }
};






wavelet w_ex, w_ey, w_g, w_two;
int dx[]={0, 0, 1, 1};
int dy[]={0, 1, 0, 1};



void init(int R, int C, int sr, int sc, int M, char *S) {
    s=S;
    int x=sr, y=sc;
    lx=rx=x;
    ly=ry=y;
    map<pair<int,int>,bool> mp;
    g.push_back({x,y});
    mp[{x,y}]=1;
    for(char c:s){
        if(c=='N') x--;
        if(c=='S') x++;
        if(c=='W') y--;
        if(c=='E') y++;
        g.push_back({x,y});
        mp[{x,y}]=1;
        lx=min(lx, x);
        rx=max(rx, x);
        ly=min(ly, y);
        ry=max(ry, y);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());

    for(auto p:g){
        int x=p.first, y=p.second;
        for(int k=0; k<4; k++){
            x+=dx[k]; y+=dy[k];
            if(mp[{x,y-1}] || mp[{x-1,y}] || mp[{x-1,y-1}] || mp[{x,y}]) two.push_back({x,y});
            if(mp[{x-1, y}] || mp[{x,y}]) ex.push_back({x,y});
            if(mp[{x, y-1}] || mp[{x,y}]) ey.push_back({x,y});
            x-=dx[k]; y-=dy[k];
        }
    }
    sort(ex.begin(), ex.end());
    sort(ey.begin(), ey.end());
    sort(two.begin(), two.end());
    ex.erase(unique(ex.begin(), ex.end()), ex.end());
    ey.erase(unique(ey.begin(), ey.end()), ey.end());
    two.erase(unique(two.begin(), two.end()), two.end());
    w_ex.init(ex);
    w_ey.init(ey);
    w_g.init(g);
    w_two.init(two);
}



int colour(int ar, int ac, int br, int bc) {
    int V=(br-ar+1)*(bc-ac+1)-w_g.rect(ar, ac, br, bc);
    int E=(br-ar+1)*(bc-ac)+(br-ar)*(bc-ac+1)-w_ex.rect(ar+1,ac,br,bc)-w_ey.rect(ar,ac+1,br,bc);
    int F=(br-ar)*(bc-ac)-w_two.rect(ar+1,ac+1,br,bc)+(ar<lx&&br>rx&&ac<ly&&bc>ry);
    // cout << V << "-" << E << "+" << F<< '\n';
    return V-E+F;
}
// add 1 face if rectangles covers region!

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

rainbow.cpp: In member function 'void wavelet::build(int, int, int)':
rainbow.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0; i<vec[x].size(); i++){
      |                      ~^~~~~~~~~~~~~~

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