oj.uz

Submission #263478

# Submission time Handle Problem Language Result Execution time Memory
263478 2020-08-13T17:36:53 Z Kastanda Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 753 ms 100968 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)
{
        // 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) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;
        int e = Get(1, lx, rx, ly, ry) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;

        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);

        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 + 1;

        return f-1 - sq;

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 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 47 ms 70780 KB Output is correct
2 Correct 52 ms 70776 KB Output is correct
3 Correct 583 ms 88944 KB Output is correct
4 Correct 678 ms 96112 KB Output is correct
5 Correct 646 ms 98664 KB Output is correct
6 Correct 589 ms 97132 KB Output is correct
7 Correct 536 ms 89448 KB Output is correct
8 Correct 340 ms 85232 KB Output is correct
9 Correct 753 ms 96764 KB Output is correct
10 Correct 673 ms 96748 KB Output is correct
11 Correct 633 ms 94440 KB Output is correct
12 Correct 255 ms 89708 KB Output is correct
13 Correct 282 ms 90860 KB Output is correct
14 Correct 272 ms 90600 KB Output is correct
15 Correct 256 ms 87784 KB Output is correct
16 Correct 568 ms 94956 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 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 50 ms 70776 KB Output isn't correct
2 Halted 0 ms 0 KB -