oj.uz

Submission #391780

# Submission time Handle Problem Language Result Execution time Memory
391780 2021-04-19T19:55:05 Z MarcoMeijer Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 3000 ms 35276 KB 
#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<<18);

int R, C, sr, sc, m;
set<ii> blue;
set<ii> points;
set<ii> edges;

struct QuadTree {
    int tot[MX];
    int child[MX][4];
    int nxt=1;
    QuadTree() {
        RE(i,N) tot[i]=0;
        RE(i,N) RE(j,4) child[i][j] = -1;
    }

    void add(int x, int y, int val, int l=0, int r=N-1, int u=0, int d=N-1, int p=0) {
        tot[p] += val;
        if(l == r)
            return;
        int mh = (l+r)/2;
        int mv = (u+d)/2;
        int cd = 0;
        if(x <= mh) cd += 1, r=mh;
        else l=mh+1;
        if(y <= mv) cd += 2, d=mv;
        else u=mv+1;
        if(child[p][cd] == -1) child[p][cd] = nxt++;
        add(x,y,val,l,r,u,d,child[p][cd]);
    }
    int get(int a, int b, int x, int y, int l=0, int r=N-1, int u=0, int d=N-1, int p=0) {
        if(p == -1) return 0;
        if(b < l || a > r || y < u || x > d) return 0;
        if(a <= l && b >= r && x <= u && y >= d) return tot[p];
        int mh = (l+r)/2;
        int mv = (u+d)/2;
        int res = 0;
        res += get(a,b,x,y,mh+1,r,mv+1,d,child[p][0]);
        res += get(a,b,x,y,l,mh,mv+1,d,child[p][1]);
        res += get(a,b,x,y,mh+1,r,u,mv,child[p][2]);
        res += get(a,b,x,y,l,mh,u,mv,child[p][3]);
        return res;
    }
} 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;
    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) {
        blueCells.add(p.fi,p.se,1);
        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  , 1);
        blueLandEdgesV.add(p.fi+1, p.se  , 1);
        if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  , 1);
        blueLandEdgesH.add(p.fi  , p.se+1, 1);
    }

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

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;
    return V - E + F - 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20940 KB Output is correct
2 Correct 22 ms 21004 KB Output is correct
3 Incorrect 19 ms 20940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20876 KB Output is correct
2 Correct 13 ms 20804 KB Output is correct
3 Execution timed out 3079 ms 29584 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20812 KB Output is correct
2 Incorrect 215 ms 35276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20940 KB Output is correct
2 Correct 22 ms 21004 KB Output is correct
3 Incorrect 19 ms 20940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20940 KB Output is correct
2 Correct 22 ms 21004 KB Output is correct
3 Incorrect 19 ms 20940 KB Output isn't correct
4 Halted 0 ms 0 KB -