oj.uz

Submission #262275

# Submission time Handle Problem Language Result Execution time Memory
262275 2020-08-12T15:23:41 Z evpipis Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 1139 ms 304000 KB 
#include <bits/stdc++.h>
using namespace std;

#include "rainbow.h"

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 2e5+5;
int n, m;
vector<ii> com[len];
set<int> mys[len];

struct node{
    int sum;
    node *lef, *rig;

    node(int s = 0, node *l = NULL, node *r = NULL){
        sum = s;
        lef = l;
        rig = r;
    }
};

typedef node *pnode;
pnode null = new node();

pnode update(pnode t, int l, int r, int i){
    pnode cur = t;
    if (cur == null)
        cur = new node(0, null, null);

    cur->sum++;

    if (l == r)
        return cur;

    int mid = (l+r)/2;
    if (i <= mid)
        cur->lef = update(t->lef, l, mid, i);
    else
        cur->rig = update(t->rig, mid+1, r, i);

    return cur;
}

int query(pnode t, int l, int r, int i, int j){
    if (r < i || j < l)
        return 0;
    if (i <= l && r <= j)
        return t->sum;

    int mid = (l+r)/2;
    return query(t->lef, l, mid, i, j) + query(t->rig, mid+1, r, i, j);
}

struct bit{
    pnode tree[len]; // try to replace with vector instead
    int rev, row, col; // pref or suf?

    bit(int x = 0, int y = 0, int r = 0){
        row = x;
        col = y;
        rev = r;
    }

    void init(){
        for (int i = 1; i < len; i++)
            tree[i] = null;
    }

    void upd(int i, int j){
        if (rev)
            i = col-i+1;

        while (i <= col)
            tree[i] = update(tree[i], 1, row, j), i += i&(-i);
    }

    int ask(int i, int l, int r){
        if (rev)
            i = col-i+1;

        int ans = 0;
        while (i > 0)
            ans += query(tree[i], 1, row, l, r), i -= i&(-i);
        return ans;
    }
};

bit pref_com, suf_com;
bit pref_edg, suf_edg;

void nex_mov(int &x, int &y, char c){
    if (c == 'N')
        x--;
    else if (c == 'S')
        x++;
    else if (c == 'W')
        y--;
    else
        y++;
}

void find_com(int x, int y, char *moves){
    int pos = 0;
    while (true){
        mys[x].insert(y);

        if (moves[pos] == '\0')
            break;
        nex_mov(x, y, moves[pos++]);
    }

    for (int row = 1; row <= n; row++){
        //printf("row%d\n", row);
        int cur = 1;
        for (auto col: mys[row]){
            //printf("%d\n", col);
            if (cur <= col-1)
                com[row].pb(mp(cur, col-1));
            cur = col+1;
        }

        //printf("cur in the end: %d\n", cur);
        //printf("n = %d, m = %d\n", n, m);
        if (cur <= m)
            com[row].pb(mp(cur, m));
    }

    for (int row = 1; row <= n; row++){
        //printf("row#%d:", row);
        for (auto cur: com[row]){
            //printf(" (%d, %d)", cur.fi, cur.se);
            pref_com.upd(cur.se, row);
            suf_com.upd(cur.fi, row);
        }
        //printf("\n");
    }
}

bool inter(ii a, ii b){
    return !(a.se < b.fi || b.se < a.fi);
}

void find_edg(){
    for (int row = 2; row <= n; row++){
        for (int i = 0, j = 0; i < com[row].size(); i++){
            while (j < com[row-1].size() && com[row-1][j].se < com[row][i].fi)
                j++;

            while (j < com[row-1].size() && inter(com[row-1][j], com[row][i])){
                int for_pref = min(com[row-1][j].se, com[row][i].se);
                int for_suf = max(com[row-1][j].fi, com[row][i].fi);

                pref_edg.upd(for_pref, row);
                suf_edg.upd(for_suf, row);

                j++;
            }

            j = max(0, j-1);
        }
    }
}

void init(int n_, int m_, int sr, int sc, int M, char *moves) {
    n = n_, m = m_;

    null->lef = null->rig = null;

    pref_com = bit(n, m);
    suf_com = bit(n, m, 1);
    pref_edg = bit(n, m);
    suf_edg = bit(n, m, 1);

    pref_com.init();
    suf_com.init();
    pref_edg.init();
    suf_edg.init();

    find_com(sr, sc, moves);
    find_edg();
}

int colour(int ar, int ac, int br, int bc) {
    int ans = pref_com.ask(m, ar, br) - pref_edg.ask(m, ar+1, br);
    ans -= pref_com.ask(ac-1, ar, br) - pref_edg.ask(ac-1, ar+1, br);
    ans -= suf_com.ask(bc+1, ar, br) - suf_edg.ask(bc+1, ar+1, br);

    return ans;
}

Compilation message

rainbow.cpp: In function 'void find_edg()':
rainbow.cpp:151:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i = 0, j = 0; i < com[row].size(); i++){
      |                                ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:152:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while (j < com[row-1].size() && com[row-1][j].se < com[row][i].fi)
      |                    ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:155:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while (j < com[row-1].size() && inter(com[row-1][j], com[row][i])){
      |                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20736 KB Output is correct
2 Correct 16 ms 21072 KB Output is correct
3 Incorrect 18 ms 20864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20608 KB Output is correct
2 Correct 13 ms 20608 KB Output is correct
3 Correct 154 ms 24288 KB Output is correct
4 Correct 169 ms 27128 KB Output is correct
5 Correct 185 ms 29176 KB Output is correct
6 Correct 175 ms 28408 KB Output is correct
7 Correct 191 ms 32760 KB Output is correct
8 Correct 159 ms 24440 KB Output is correct
9 Correct 179 ms 29944 KB Output is correct
10 Correct 190 ms 31992 KB Output is correct
11 Correct 187 ms 31352 KB Output is correct
12 Correct 105 ms 28664 KB Output is correct
13 Correct 107 ms 29980 KB Output is correct
14 Correct 115 ms 31992 KB Output is correct
15 Correct 112 ms 31356 KB Output is correct
16 Correct 194 ms 27580 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20608 KB Output is correct
2 Correct 253 ms 81844 KB Output is correct
3 Correct 1139 ms 294904 KB Output is correct
4 Correct 855 ms 304000 KB Output is correct
5 Correct 774 ms 212344 KB Output is correct
6 Correct 267 ms 82936 KB Output is correct
7 Incorrect 293 ms 86808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20736 KB Output is correct
2 Correct 16 ms 21072 KB Output is correct
3 Incorrect 18 ms 20864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20736 KB Output is correct
2 Correct 16 ms 21072 KB Output is correct
3 Incorrect 18 ms 20864 KB Output isn't correct
4 Halted 0 ms 0 KB -