oj.uz

Submission #263491

# Submission time Handle Problem Language Result Execution time Memory
263491 2020-08-13T17:53:55 Z Kastanda Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 630 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);
                // 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);

        int f = e - v + 1 + c;

        return f-1 - sq;

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70808 KB Output is correct
2 Correct 46 ms 70760 KB Output is correct
3 Correct 416 ms 86384 KB Output is correct
4 Correct 630 ms 95976 KB Output is correct
5 Correct 628 ms 94724 KB Output is correct
6 Correct 407 ms 88168 KB Output is correct
7 Correct 463 ms 85612 KB Output is correct
8 Correct 220 ms 78312 KB Output is correct
9 Correct 620 ms 92908 KB Output is correct
10 Correct 614 ms 92524 KB Output is correct
11 Correct 468 ms 88340 KB Output is correct
12 Correct 248 ms 87136 KB Output is correct
13 Correct 257 ms 88172 KB Output is correct
14 Correct 262 ms 87788 KB Output is correct
15 Correct 248 ms 85096 KB Output is correct
16 Correct 426 ms 88812 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 70776 KB Output is correct
2 Incorrect 163 ms 100844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -