제출 #106662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106662		polyfish	무지개나라 (APIO17_rainbow)	C++14	50 / 100	1006 ms	1049600 KiB

rainbow

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};
const int INF = 1e9;

struct fenwick_tree_2D {

    int m, n;
    vector<vector<int> > bit;

    void init(int _m, int _n) {
        m = _m;
        n = _n;
        bit.resize(m+1);
        for (int i=0; i<=m; ++i)
            bit[i].resize(n+1);
    }

    void add(int x, int y) {
        if (!bit[x][y])
            ++bit[x][y];
    }

    void process() {
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j)
                bit[i][j] += bit[i-1][j] + bit[i][j-1] - bit[i-1][j-1];
        }
    }

    int get(int x1, int y1, int x2, int y2) {
        if (x1>x2 || y1>y2)
            return 0;
        return bit[x2][y2] - bit[x2][y1-1] - bit[x1-1][y2] + bit[x1-1][y1-1];
    }
};

int m, n, min_x, max_x, min_y, max_y;
vector<pair<int, int> > snake;
bool visited[52][52];
fenwick_tree_2D T1, T2, R, C;

void add(pair<int, int> p) {
    T1.add(p.first, p.second);

    for (int i=0; i<4; ++i) {
        T2.add(p.first, p.second);
        p.first += X[i];
        p.second += Y[i];
    }

    C.add(p.first, p.second);
    C.add(p.first, p.second+1);
    R.add(p.first, p.second);
    R.add(p.first+1, p.second);
}

void init(int _R, int _C, int sr, int sc, int M, char *S) {
    m = _R;
    n = _C;
    max_x = max_y = -INF;
    min_x = min_y = INF;

    snake.resize(M+1);
    snake[0] = {sr, sc};
    for (int i=1; i<=M; ++i) {
        snake[i] = snake[i-1];
        if (S[i-1]=='N')
            --snake[i].first;
        else if (S[i-1]=='S')
            ++snake[i].first;
        else if (S[i-1]=='W')
            --snake[i].second;
        else
            ++snake[i].second;
    }

    sort(snake.begin(), snake.end());
    snake.resize(unique(snake.begin(), snake.end()) - snake.begin());

    T1.init(m+1, n+1);
    T2.init(m+1, n+1);
    R.init(m+1, n+1);
    C.init(m+1, n+1);

    for (auto p : snake) {
        min_x = min(min_x, p.first);
        max_x = max(max_x, p.first);
        min_y = min(min_y, p.second);
        max_y = max(max_y, p.second);

        add(p);
    }

    T1.process();
    T2.process();
    R.process();
    C.process();
}

int subtask3(int x1, int y1, int x2, int y2) {
    set<pair<int, int> > v;
    set<pair<pair<int, int>, pair<int, int> > > e;

    int res = 0;

    for (int i=x1; i<=x2+1; ++i) {
        v.insert({i, y1});
        v.insert({i, y2+1});
        if (i<=x2) {
            pair<int, int> tmp1(i, y1), tmp2(i+1, y1);
            e.insert({min(tmp1, tmp2), max(tmp1, tmp2)});
            pair<int, int> tmp3(i, y2+1), tmp4(i+1, y2+1);
            e.insert({min(tmp3, tmp4), max(tmp3, tmp4)});
        }
    }

    for (int i=y1; i<=y2+1; ++i) {
        v.insert({x1, i});
        v.insert({x2+1, i});
        if (i<=y2) {
            pair<int, int> tmp1(x1, i), tmp2(x1, i+1);
            e.insert({min(tmp1, tmp2), max(tmp1, tmp2)});
            pair<int, int> tmp3(x2+1, i), tmp4(x2+1, i+1);
            e.insert({min(tmp3, tmp4), max(tmp3, tmp4)});
        }
    }

    for (auto p : snake) {
        if (x1<=p.first && p.first<=x2 && y1<=p.second && p.second<=y2) {
            --res;
            for (int i=0; i<4; ++i) {
                v.insert(p);
                pair<int, int> tmp = p;
                p.first += X[i];
                p.second += Y[i];
                e.insert({min(p, tmp), max(p, tmp)});
            }
        }
    }
//    debug(v.size());
//    debug(e.size());

    res += (int)e.size() - (int)v.size() + 1;

    if (x1<min_x && max_x<x2 && y1<min_y && max_y<y2)
        ++res;

    return res;
}

int colour(int x1, int y1, int x2, int y2) {
    if (1LL*m*n>1000000)
        return subtask3(x1, y1, x2, y2);

    int v = T2.get(x1+1, y1+1, x2, y2);
    int e = R.get(x1+1, y1, x2, y2) + C.get(x1, y1+1, x2, y2);
//    debug(R.get(x1+1, y1+1, x2, y2-1));

    int res = e - v + 1;
    if (x1<min_x && max_x<x2 && y1<min_y && max_y<y2)
        ++res;
    res -= T1.get(x1, y1, x2, y2);

    return res;
}

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