Submission #262938

#	Time	Username	Problem	Language	Result	Execution time	Memory
262938		evpipis	Land of the Rainbow Gold (APIO17_rainbow)	C++11	12 / 100	3077 ms	32996 KiB

rainbow

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

#include "rainbow.h"

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 2e5+5;
int n, m, min_r = len, max_r = 0, min_c = len, max_c = 0;

struct bit{
    vector<int> vec[len];
    int row, col;

    bit(int x = 0, int y = 0){
        row = x;
        col = y;
    }

    void init(){
        for (int i = row; i >= 1; i--){
            sort(vec[i].begin(), vec[i].end());
            vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());

            for (int j = i+(i&(-i)); j <= row; j += i&(-i))
                for (auto &c: vec[i]) vec[j].pb(c);
        }

        for (int i = 1; i <= row; i++)
            sort(vec[i].begin(), vec[i].end());
    }

    void upd(int i, int j){
        vec[i].pb(j);
    }

    int ask(int i, int l, int r){
        int ans = 0;
        while (i > 0){
            ans += upper_bound(vec[i].begin(), vec[i].end(), r) - lower_bound(vec[i].begin(), vec[i].end(), l);
            i -= i&(-i);
        }
        return ans;
    }

    int query(int ar, int br, int ac, int bc){
        return ask(br, ac, bc) - ask(ar-1, ac, bc);
    }

    void print(int row){
        printf("row#%d:", row);
        for (int j = 0; j < vec[row].size(); j++)
            printf(" %d", vec[row][j]);
        printf("\n");
    }
};

bit vertices, rivers;
bit vertical, horizontal;

void nex_mov(int &x, int &y, char &c){
    if (c == 'N')
        x--;
    else if (c == 'S')
        x++;
    else if (c == 'W')
        y--;
    else
        y++;
}

void add_block(int x, int y){
    min_r = min(min_r, x);
    max_r = max(max_r, x);
    min_c = min(min_c, y);
    max_c = max(max_c, y);

    rivers.upd(x, y);

    vertices.upd(x, y);
    vertices.upd(x+1, y);
    vertices.upd(x, y+1);
    vertices.upd(x+1, y+1);

    vertical.upd(x, y);
    vertical.upd(x, y+1);

    horizontal.upd(x, y);
    horizontal.upd(x+1, y);
}

void make_graph(int x, int y, char *moves){
    int pos = 0;
    while (true){
        add_block(x, y);

        if (moves[pos] == '\0')
            break;
        nex_mov(x, y, moves[pos++]);
    }
}

void init(int n_, int m_, int sr, int sc, int M, char *moves) {
    n = n_, m = m_;

    vertices = bit(n+1, m+1);
    rivers = bit(n, m);
    vertical = bit(n, m+1);
    horizontal = bit(n+1, m);

    make_graph(sr, sc, moves);

    vertices.init();
    rivers.init();
    vertical.init();
    horizontal.init();
}

int colour(int ar, int ac, int br, int bc) {
    int v = vertices.query(ar+1, br, ac+1, bc); // + 2*(length+width)
    int e = vertical.query(ar, br, ac+1, bc); // + 2*length
    e += horizontal.query(ar+1, br, ac, bc); // + 2*width
    int r = rivers.query(ar, br, ac, bc);
    int c = (ar >= min_r || max_r >= br || ac >= min_c || max_c >= bc)?1:2;

    //printf("v = %d, e = %d, r = %d, c = %d\n", v, e, r, c);

    return e + c - v - r;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void bit::print(int)':
rainbow.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < vec[row].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~

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