Submission #392096

#	Time	Username	Problem	Language	Result	Execution time	Memory
392096		MarcoMeijer	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3095 ms	472712 KiB

rainbow

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = (1<<22);
const int N = (1<<19);

int R, C, sr, sc, m;
set<ii> blue;
set<ii> points;
set<ii> edges;
int minR, maxR, minC, maxC;

int root=0;

struct QuadTree {
    int seg1[MX];
    int point1[MX];
    int child1[MX][2];
    int nxt1=0;

    int seg2[MX];
    int child2[MX][2];
    int nxt2=1;

    QuadTree() {
        RE(i,MX) seg1[i]=0;
        RE(i,MX) seg2[i]=-1;
        RE(i,MX) RE(j,2) child1[i][j] = child2[i][j] = -1;
    }

    void add1(int x, int l, int r, int& p) {
        if(p == -1) p = nxt1++;

        seg1[p]++;
        if(l == r) return;
        int m = (l+r)/2;
        if(seg1[p] == 1) {
            point1[p] = x;
            return;
        }
        if(point1[p] != -1) {
            int y = point1[p];
            if(y <= m) add1(y, l  , m, child1[p][0]);
            else       add1(y, m+1, r, child1[p][1]);
            point1[p] = -1;
        }
        if(x <= m) add1(x, l  , m, child1[p][0]);
        else       add1(x, m+1, r, child1[p][1]);
    }
    void add(int x, int y, int l=0, int r=N-1, int& p=root) {
        if(p == -1) p = nxt2++;

        add1(y, 0, N-1, seg2[p]);
        if(l == r) return;
        int m = (l+r)/2;
        if(x <= m) add(x, y, l  , m, child2[p][0]);
        else       add(x, y, m+1, r, child2[p][1]);
    }
    int get1(int i, int j, int l, int r, int p) {
        if(j < l || i > r) return 0;
        if(p == -1) return 0;
        if(i <= l && j >= r) return seg1[p];
        if(point1[p] != -1) return i <= point1[p] && point1[p] <= j;
        int m = (l+r)/2;
        int a = get1(i, j, l  , m, child1[p][0]);
        int b = get1(i, j, m+1, r, child1[p][1]);
        return a+b;
    }
    int get(int i, int j, int x, int y, int l=0, int r=N-1, int p=root) {
        if(j < l || i > r) return 0;
        if(p == -1) return 0;
        if(i <= l && j >= r) return get1(x,y,0,N-1,seg2[p]);
        int m = (l+r)/2;
        int a = get(i, j, x, y, l  , m, child2[p][0]);
        int b = get(i, j, x, y, m+1, r, child2[p][1]);
        return a+b;
    }
} blueCells, bluePoints, blueLandEdgesH, blueLandEdgesV;

void init(int _R, int _C, int _sr, int _sc, int M, char *S) {
    R=_R; C=_C; sr=_sr; sc=_sc;
    minR=maxR=sr;
    minC=maxC=sc;
    RE(i,M) {
        blue.insert({sc,sr});
        if(S[i] == 'N') sr--;
        if(S[i] == 'S') sr++;
        if(S[i] == 'E') sc++;
        if(S[i] == 'W') sc--;
    }
    blue.insert({sc,sr});

    FOR(p,blue) {
        minR = min(minR, p.se);
        minC = min(minC, p.fi);
        maxR = max(maxR, p.se);
        maxC = max(maxC, p.fi);
        blueCells.add(p.fi,p.se);
        points.insert({p.fi  ,p.se  });
        points.insert({p.fi  ,p.se+1});
        points.insert({p.fi+1,p.se  });
        points.insert({p.fi+1,p.se+1});

        if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
                                         blueLandEdgesV.add(p.fi+1, p.se  );
        if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
                                         blueLandEdgesH.add(p.fi  , p.se+1);
    }

    FOR(p,points)
        bluePoints.add(p.fi,p.se);
}

int colour(int ar, int ac, int br, int bc) {
    int blueCellsCnt  = blueCells .get(ac  ,bc,ar  ,br);
    int bluePointsCnt = bluePoints.get(ac+1,bc,ar+1,br);
    int blueLandEdges = blueLandEdgesH.get(ac,bc,ar+1,br) + blueLandEdgesV.get(ac+1,bc,ar,br);
    int W = bc - ac + 1;
    int H = br - ar + 1;
    int V = W*H - blueCellsCnt;
    int F = (W-1)*(H-1) - bluePointsCnt + 1;
    int E = (W-1)*H + (H-1)*W - blueLandEdges;

    if(ar < minR && maxR < br && ac < minC && maxC < bc)
        F++;

    return V - E + F - 1;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:131:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  131 |         if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:132:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  132 |                                          blueLandEdgesV.add(p.fi+1, p.se  );
      |                                          ^~~~~~~~~~~~~~
rainbow.cpp:133:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  133 |         if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:134:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  134 |                                          blueLandEdgesH.add(p.fi  , p.se+1);
      |                                          ^~~~~~~~~~~~~~

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