oj.uz

Submission #263503

# Submission time Handle Problem Language Result Execution time Memory
263503 2020-08-13T18:08:30 Z Kastanda Land of the Rainbow Gold (APIO17_rainbow) C++11
50 / 100
 1061 ms 104048 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);
                // South-West :
                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 - 1);
                // 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70776 KB Output is correct
2 Correct 50 ms 71012 KB Output is correct
3 Correct 51 ms 71032 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 50 ms 71160 KB Output is correct
6 Correct 49 ms 70824 KB Output is correct
7 Correct 52 ms 70828 KB Output is correct
8 Correct 45 ms 70776 KB Output is correct
9 Correct 52 ms 70776 KB Output is correct
10 Correct 60 ms 70776 KB Output is correct
11 Correct 56 ms 71032 KB Output is correct
12 Correct 64 ms 71032 KB Output is correct
13 Correct 56 ms 71160 KB Output is correct
14 Correct 65 ms 71160 KB Output is correct
15 Correct 52 ms 70784 KB Output is correct
16 Correct 57 ms 70752 KB Output is correct
17 Correct 65 ms 70776 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 70752 KB Output is correct
2 Correct 65 ms 70776 KB Output is correct
3 Correct 476 ms 86244 KB Output is correct
4 Correct 679 ms 95984 KB Output is correct
5 Correct 640 ms 95080 KB Output is correct
6 Correct 411 ms 88552 KB Output is correct
7 Correct 477 ms 86896 KB Output is correct
8 Correct 210 ms 78440 KB Output is correct
9 Correct 677 ms 93036 KB Output is correct
10 Correct 592 ms 93164 KB Output is correct
11 Correct 466 ms 88808 KB Output is correct
12 Correct 270 ms 87148 KB Output is correct
13 Correct 281 ms 88304 KB Output is correct
14 Correct 300 ms 88424 KB Output is correct
15 Correct 274 ms 85484 KB Output is correct
16 Correct 494 ms 88936 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70784 KB Output is correct
2 Incorrect 188 ms 100972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70776 KB Output is correct
2 Correct 50 ms 71012 KB Output is correct
3 Correct 51 ms 71032 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 50 ms 71160 KB Output is correct
6 Correct 49 ms 70824 KB Output is correct
7 Correct 52 ms 70828 KB Output is correct
8 Correct 45 ms 70776 KB Output is correct
9 Correct 52 ms 70776 KB Output is correct
10 Correct 60 ms 70776 KB Output is correct
11 Correct 56 ms 71032 KB Output is correct
12 Correct 64 ms 71032 KB Output is correct
13 Correct 56 ms 71160 KB Output is correct
14 Correct 65 ms 71160 KB Output is correct
15 Correct 52 ms 70784 KB Output is correct
16 Correct 57 ms 70752 KB Output is correct
17 Correct 65 ms 70776 KB Output is correct
18 Correct 1061 ms 101896 KB Output is correct
19 Correct 186 ms 76408 KB Output is correct
20 Correct 170 ms 74772 KB Output is correct
21 Correct 167 ms 75608 KB Output is correct
22 Correct 184 ms 75768 KB Output is correct
23 Correct 183 ms 76280 KB Output is correct
24 Correct 245 ms 74872 KB Output is correct
25 Correct 209 ms 76024 KB Output is correct
26 Correct 191 ms 76280 KB Output is correct
27 Correct 466 ms 93420 KB Output is correct
28 Correct 614 ms 93280 KB Output is correct
29 Correct 579 ms 95856 KB Output is correct
30 Correct 726 ms 104048 KB Output is correct
31 Correct 52 ms 70904 KB Output is correct
32 Correct 694 ms 85820 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70776 KB Output is correct
2 Correct 50 ms 71012 KB Output is correct
3 Correct 51 ms 71032 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 50 ms 71160 KB Output is correct
6 Correct 49 ms 70824 KB Output is correct
7 Correct 52 ms 70828 KB Output is correct
8 Correct 45 ms 70776 KB Output is correct
9 Correct 52 ms 70776 KB Output is correct
10 Correct 60 ms 70776 KB Output is correct
11 Correct 56 ms 71032 KB Output is correct
12 Correct 64 ms 71032 KB Output is correct
13 Correct 56 ms 71160 KB Output is correct
14 Correct 65 ms 71160 KB Output is correct
15 Correct 52 ms 70784 KB Output is correct
16 Correct 57 ms 70752 KB Output is correct
17 Correct 65 ms 70776 KB Output is correct
18 Correct 1061 ms 101896 KB Output is correct
19 Correct 186 ms 76408 KB Output is correct
20 Correct 170 ms 74772 KB Output is correct
21 Correct 167 ms 75608 KB Output is correct
22 Correct 184 ms 75768 KB Output is correct
23 Correct 183 ms 76280 KB Output is correct
24 Correct 245 ms 74872 KB Output is correct
25 Correct 209 ms 76024 KB Output is correct
26 Correct 191 ms 76280 KB Output is correct
27 Correct 466 ms 93420 KB Output is correct
28 Correct 614 ms 93280 KB Output is correct
29 Correct 579 ms 95856 KB Output is correct
30 Correct 726 ms 104048 KB Output is correct
31 Correct 52 ms 70904 KB Output is correct
32 Correct 694 ms 85820 KB Output is correct
33 Incorrect 188 ms 100972 KB Output isn't correct
34 Halted 0 ms 0 KB -