oj.uz

Submission #262273

# Submission time Handle Problem Language Result Execution time Memory
262273 2020-08-12T15:19:25 Z evpipis Land of the Rainbow Gold (APIO17_rainbow) C++11
0 / 100
 1161 ms 303972 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 = 1; 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--;
        }
    }
}

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 Incorrect 17 ms 21120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20608 KB Output is correct
2 Correct 13 ms 20608 KB Output is correct
3 Correct 169 ms 27128 KB Output is correct
4 Correct 167 ms 30080 KB Output is correct
5 Correct 189 ms 31992 KB Output is correct
6 Incorrect 200 ms 31352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20608 KB Output is correct
2 Correct 250 ms 81892 KB Output is correct
3 Correct 1161 ms 294908 KB Output is correct
4 Incorrect 859 ms 303972 KB Output isn't correct
5 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 Incorrect 17 ms 21120 KB Output isn't correct
3 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 Incorrect 17 ms 21120 KB Output isn't correct
3 Halted 0 ms 0 KB -