제출 #258601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258601		Mercenary	무지개나라 (APIO17_rainbow)	C++14	100 / 100	1134 ms	68952 KiB

rainbow

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int maxn = 2e5 + 5;

struct BIT{
    vector<int> s[maxn];
    void init(){
        for(int i = maxn - 1 ; i >= 1 ; --i){
            sort(s[i].begin(),s[i].end());
            s[i].erase(unique(s[i].begin(),s[i].end()),s[i].end());
            for(int x = i + (i & -i) ; x < maxn ; x += x & -x){
                for(auto &c : s[i])s[x].pb(c);
            }
        }
        for(int i = 1 ; i < maxn ; ++i)sort(s[i].begin(),s[i].end());
    }
    void add(int x , int y){s[x].pb(y);}
    int query(int l , int r , int L , int R){
        if(L > R || l > r)return 0;
        int res = 0;
        for(int x = l - 1 ; x > 0 ; x &= x - 1){
            res -= upper_bound(s[x].begin(),s[x].end(),R) - lower_bound(s[x].begin(),s[x].end(),L);
        }
        for(int x = r ; x > 0 ; x &= x - 1){
            res += upper_bound(s[x].begin(),s[x].end(),R) - lower_bound(s[x].begin(),s[x].end(),L);
        }
        return res;
    }
}vertical , horizontal , vertices , rivers;

int mx_r, mn_r, mx_c, mn_c;
void add(int x, int y) {
    vertices.add(x, y);
    vertices.add(x + 1, y);
    vertices.add(x, y + 1);
    vertices.add(x + 1, y + 1);
    horizontal.add(x, y);
    horizontal.add(x + 1, y);
    vertical.add(x, y);
    vertical.add(x, y + 1);
    rivers.add(x, y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    mx_r = mn_r = sr;
    mx_c = mn_c = sc;
    add(sr,sc);
    for(int i = 0 ; i < M ; ++i){
        if (S[i] == 'N') sr--;
        if (S[i] == 'E') sc++;
        if (S[i] == 'S') sr++;
        if (S[i] == 'W') sc--;
        add(sr, sc);
        mx_r = max(mx_r, sr);
        mn_r = min(mn_r, sr);
        mx_c = max(mx_c, sc);
        mn_c = min(mn_c, sc);
    }
    vertical.init();horizontal.init();vertices.init();rivers.init();

}

int colour(int ar, int ac, int br, int bc) {
    int E = horizontal.query(ar + 1, br, ac, bc) + vertical.query(ar, br, ac + 1, bc);
    int V = vertices.query(ar + 1, br, ac + 1, bc);
    int R = rivers.query(ar, br, ac, bc);
    int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
    return E - V + C - R;
}

#ifdef LOCAL

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

#endif // LOCAL

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