Submission #911116

#	Time	Username	Problem	Language	Result	Execution time	Memory
911116		lighton	Land of the Rainbow Gold (APIO17_rainbow)	C++17	50 / 100	546 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
using namespace std;
typedef long long ll;
int r,c;
int minr,maxr,minc,maxc;
struct ST{
    int row,col;
    vector<vector<int> > arr;
    vector<vector<int> > ps;
    void init(int R, int C){
        row = R;
        col = C;
        arr.resize(R+2,vector<int>(C+2,0));
        ps.resize(R+2,vector<int>(C+2,0));
    }
    void psum(){
        forf(i,1,row+1){
            forf(j,1,col+1){
                ps[i][j] = arr[i][j]+ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
            }
        }
    }
    int query(int r1, int c1, int r2, int c2){
        return ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
    }
} F,V,Ex,Ey;

void mark(int row, int col){
    F.arr[row][col] = 1;
    V.arr[row][col] = 1; V.arr[row+1][col] = 1; V.arr[row][col+1] = 1; V.arr[row+1][col+1] = 1;
    Ex.arr[row][col] = 1; Ex.arr[row+1][col] = 1;
    Ey.arr[row][col] = 1; Ey.arr[row][col+1] = 1;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    r=R;c=C;
    F.init(r,c);V.init(r,c);Ex.init(r,c);Ey.init(r,c);

    int row = sr, col =sc;
    minr = row; maxr = row; minc = col; maxc = col;
    mark(row,col);
    forf(i,0,M-1){
        if(S[i] == 'N') row--;
        if(S[i] == 'S') row++;
        if(S[i] == 'E') col++;
        if(S[i] == 'W') col--;
        mark(row,col);
        minr = min(minr,row); maxr = max(maxr,row);
        minc = min(minc,col); maxc = max(maxc,col);
    }

    F.psum();V.psum();Ex.psum();Ey.psum();
}

int colour(int ar, int ac, int br, int bc) {
    int f = F.query(ar,ac,br,bc);
    int v = V.query(ar+1,ac+1,br,bc);
    int ex = Ex.query(ar+1,ac,br,bc);
    int ey = Ey.query(ar,ac+1,br,bc);
    int p = 0;
    if(ar<minr && br>maxr && ac<minc && bc>maxc) p = 1;
    return 1-v+ex+ey-f+p;
}

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