oj.uz

답안 #263496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263496 2020-08-13T18:02:43 Z Kastanda 무지개나라 (APIO17_rainbow) C++11
12 / 100
 644 ms 100844 KB 
// M
#include<bits/stdc++.h>
#include "rainbow.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 200005;
int n, m;
vector < int > V[3][N], VS[3][N * 2], R[2][N], C[2][N];
vector < pair < int , int > > A;
map < int , int > MP[N];
inline int Count(vector < int > &vec, int l, int r)
{
        // [l, r)
        return (int)(lower_bound(vec.begin(), vec.end(), r) - lower_bound(vec.begin(), vec.end(), l));
}
void Build(int id = 1, int l = 1, int r = n + 1)
{
        if (r - l < 2)
        {
                for (int w = 0; w <= 2; w ++)
                {
                        VS[w][id] = V[w][l];
                        sort(VS[w][id].begin(), VS[w][id].end());
                }
                return ;
        }
        Build(lc, l, md);
        Build(rc, md, r);
        for (int w = 0; w <= 2; w ++)
                merge(VS[w][lc].begin(), VS[w][lc].end(), VS[w][rc].begin(), VS[w][rc].end(), back_inserter(VS[w][id]));
}
int Get(int w, int le, int ri, int lq, int rq, int id = 1, int l = 1, int r = n + 1)
{
        if (ri <= l || r <= le)
                return 0;
        if (le <= l && r <= ri)
                return Count(VS[w][id], lq, rq);
        return Get(w, le, ri, lq, rq, lc, l, md) + Get(w, le, ri, lq, rq, rc, md, r);
}
void init(int _n, int _m, int sta, int stb, int k, char * S)
{
        n = _n; m = _m;
        int nwa = sta, nwb = stb;
        A.push_back(make_pair(nwa, nwb));
        for (int i = 0; i < k; i ++)
        {
                if (S[i] == 'N') nwa --;
                if (S[i] == 'S') nwa ++;
                if (S[i] == 'W') nwb --;
                if (S[i] == 'E') nwb ++;
                A.push_back(make_pair(nwa, nwb));
        }
        sort(A.begin(), A.end());
        A.resize(unique(A.begin(), A.end()) - A.begin());
        for (auto a : A)
                MP[a.first][a.second] = 1;
        // w = 0 is for vertices ..
        for (auto a : A)
                V[0][a.first].push_back(a.second);
        // w = 1 is for edges ..
        for (auto a : A)
        {
                // South :
                if (MP[a.first + 1][a.second])
                        V[1][a.first].push_back(a.second),
                        C[1][a.second].push_back(a.first);
                // East :
                if (MP[a.first][a.second + 1])
                        V[1][a.first].push_back(a.second),
                        R[1][a.first].push_back(a.second);
                // South-East :
                if (!MP[a.first][a.second + 1] && !MP[a.first + 1][a.second] && MP[a.first + 1][a.second + 1])
                        V[1][a.first].push_back(a.second);
                // w = 2 is for squares ..
                if (MP[a.first + 1][a.second] && MP[a.first][a.second + 1] && MP[a.first + 1][a.second + 1])
                        V[2][a.first].push_back(a.second);
        }
        Build();
        for (auto a : A)
                R[0][a.first].push_back(a.second),
                C[0][a.second].push_back(a.first);
        for (int i = 1; i <= n; i ++)
                for (int w = 0; w <= 1; w ++)
                        sort(R[w][i].begin(), R[w][i].end());
        for (int i = 1; i <= m; i ++)
                for (int w = 0; w <= 1; w ++)
                        sort(C[w][i].begin(), C[w][i].end());
}
int colour(int lx, int ly, int rx, int ry)
{
        // Note : if no river cell is on the border, then c = 2.
        // v - e + f = 1 + c  ~~~>  f = e - v + 1 + c
        // sq : number of 2*2 squares
        // Then the answer is f-1 - sq
        int v = Get(0, lx, rx + 1, ly, ry + 1);

        if (v == 0) // No river cell
                return 1;

        v += (rx - lx + 1 + ry - ly + 1) * 2 + 4;

        int e = Get(1, lx, rx, ly, ry) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;

        int stamp = e;

        e += Count(R[0][lx], ly, ry + 1);
        e += Count(R[0][rx], ly, ry + 1);
        e += Count(C[0][ly], lx, rx + 1);
        e += Count(C[0][ry], lx, rx + 1);

        int c = 1;
        if (e == stamp) // There is no border river cell
                c = 2;

        e += Count(R[1][rx], ly, ry);
        e += Count(C[1][ry], lx, rx);

        int sq = MP[lx][ly] + MP[lx][ry] + MP[rx][ly] + MP[rx][ry];

        sq += Get(2, lx, rx, ly, ry);
        sq += Count(R[1][lx], ly, ry);
        sq += Count(R[1][rx], ly, ry);
        sq += Count(C[1][ly], lx, rx);
        sq += Count(C[1][ry], lx, rx);

        /*printf("v is : %d\n", v);
        printf("e is : %d\n", e);
        printf("c is : %d\n", c);
        printf("sq is : %d\n", sq);*/

        int f = e - v + 1 + c;

        //printf("f is : %d\n", f);

        return f-1 - sq;

}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 70784 KB Output is correct
2 Correct 44 ms 70780 KB Output is correct
3 Correct 426 ms 86080 KB Output is correct
4 Correct 635 ms 95688 KB Output is correct
5 Correct 644 ms 94740 KB Output is correct
6 Correct 425 ms 88424 KB Output is correct
7 Correct 481 ms 86508 KB Output is correct
8 Correct 214 ms 78312 KB Output is correct
9 Correct 625 ms 92908 KB Output is correct
10 Correct 565 ms 92524 KB Output is correct
11 Correct 474 ms 88728 KB Output is correct
12 Correct 265 ms 86944 KB Output is correct
13 Correct 271 ms 88044 KB Output is correct
14 Correct 276 ms 87976 KB Output is correct
15 Correct 288 ms 85096 KB Output is correct
16 Correct 486 ms 88724 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70904 KB Output is correct
2 Incorrect 169 ms 100844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -