Submission #969981

#	Time	Username	Problem	Language	Result	Execution time	Memory
969981		socpite	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	984 ms	140288 KiB

rainbow

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

const int maxn = 2e5+5;

vector<int> pos[4][maxn];
vector<int> FW[4][maxn];

vector<pair<int, int>> E[4];

int r, c;

void fadd(int x, int y, int id){
    for(x; x <= r; x += x&(-x))pos[id][x].push_back(y);
}

void add(int x, int y, int id){
    for(x; x <= r; x += x&(-x)){
        for(int idx = lower_bound(pos[id][x].begin(), pos[id][x].end(), y) - pos[id][x].begin(); idx < FW[id][x].size(); idx += idx&(-idx)){
            FW[id][x][idx]++;
        }
    }
}

int query(int x, int y, int id){
    int re = 0;
    for(x; x > 0; x -= x&(-x)){
        for(int idx = upper_bound(pos[id][x].begin(), pos[id][x].end(), y) - pos[id][x].begin() - 1; idx > 0; idx -= idx&(-idx)){
            re += FW[id][x][idx];
        }
    }
    return re;
}

int query_rect(int x1, int y1, int x2, int y2, int id){
    if(x1 > x2 || y1 > y2)return 0;
    return query(x2, y2, id) - query(x1-1, y2, id) - query(x2, y1-1, id) + query(x1-1, y1-1, id);
}

void add_square(int sr, int sc){
    // cout << sr << " " << sc << endl;
    E[0].push_back({sr, sc});
    E[0].push_back({sr+1, sc});

    E[1].push_back({sr, sc});
    E[1].push_back({sr, sc+1});

    E[2].push_back({sr, sc});

    E[3].push_back({sr, sc});
    E[3].push_back({sr, sc+1});
    E[3].push_back({sr+1, sc+1});
    E[3].push_back({sr+1, sc});
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R;
    c = C;
    add_square(sr, sc);
    for(int i = 0; i < M; i++){
        if(S[i] == 'N')sr--;
        else if(S[i] == 'W')sc--;
        else if(S[i] == 'S')sr++;
        else sc++;
        add_square(sr, sc);
    }
    for(int id = 0; id < 4; id++){
        sort(E[id].begin(), E[id].end());
        E[id].erase(unique(E[id].begin(), E[id].end()), E[id].end());
        for(auto v: E[id])fadd(v.first, v.second, id);

        for(int i = 1; i <= r; i++){
            pos[id][i].push_back(-1);
            sort(pos[id][i].begin(), pos[id][i].end());
            pos[id][i].erase(unique(pos[id][i].begin(), pos[id][i].end()), pos[id][i].end());
            FW[id][i].assign(pos[id][i].size(), 0);
        }

        for(auto v: E[id])add(v.first, v.second, id);                                     
    }
    
}

// V - E + F - C = 1 => F = 1 + C + E - V
// 

int colour(int ar, int ac, int br, int bc) {
    int F = query_rect(ar, ac, br, bc, 2);
    if(F == 0)return 1;
    int V = (br - ar + 1)*2 + (bc - ac + 1)*2 + query_rect(ar+1, ac+1, br, bc, 3);
    int E = (br - ar + 1)*2 + (bc - ac + 1)*2 + query_rect(ar+1, ac, br, bc, 0) + query_rect(ar, ac+1, br, bc, 1);
    int C = 1 + (query_rect(ar+1, ac+1, br-1, bc-1, 2) == F);
    F++;
    return 1 + C + E - V - F;
}

Compilation message (stderr)

rainbow.cpp: In function 'void fadd(int, int, int)':
rainbow.cpp:15:9: warning: statement has no effect [-Wunused-value]
   15 |     for(x; x <= r; x += x&(-x))pos[id][x].push_back(y);
      |         ^
rainbow.cpp: In function 'void add(int, int, int)':
rainbow.cpp:19:9: warning: statement has no effect [-Wunused-value]
   19 |     for(x; x <= r; x += x&(-x)){
      |         ^
rainbow.cpp:20:102: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int idx = lower_bound(pos[id][x].begin(), pos[id][x].end(), y) - pos[id][x].begin(); idx < FW[id][x].size(); idx += idx&(-idx)){
      |                                                                                                  ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int query(int, int, int)':
rainbow.cpp:28:9: warning: statement has no effect [-Wunused-value]
   28 |     for(x; x > 0; x -= x&(-x)){
      |         ^

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