oj.uz

Submission #262938

# Submission time Handle Problem Language Result Execution time Memory
262938 2020-08-13T11:16:09 Z evpipis Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 3000 ms 32996 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, min_r = len, max_r = 0, min_c = len, max_c = 0;

struct bit{
    vector<int> vec[len];
    int row, col;

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

    void init(){
        for (int i = row; i >= 1; i--){
            sort(vec[i].begin(), vec[i].end());
            vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());

            for (int j = i+(i&(-i)); j <= row; j += i&(-i))
                for (auto &c: vec[i]) vec[j].pb(c);
        }

        for (int i = 1; i <= row; i++)
            sort(vec[i].begin(), vec[i].end());
    }

    void upd(int i, int j){
        vec[i].pb(j);
    }

    int ask(int i, int l, int r){
        int ans = 0;
        while (i > 0){
            ans += upper_bound(vec[i].begin(), vec[i].end(), r) - lower_bound(vec[i].begin(), vec[i].end(), l);
            i -= i&(-i);
        }
        return ans;
    }

    int query(int ar, int br, int ac, int bc){
        return ask(br, ac, bc) - ask(ar-1, ac, bc);
    }

    void print(int row){
        printf("row#%d:", row);
        for (int j = 0; j < vec[row].size(); j++)
            printf(" %d", vec[row][j]);
        printf("\n");
    }
};

bit vertices, rivers;
bit vertical, horizontal;

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 add_block(int x, int y){
    min_r = min(min_r, x);
    max_r = max(max_r, x);
    min_c = min(min_c, y);
    max_c = max(max_c, y);

    rivers.upd(x, y);

    vertices.upd(x, y);
    vertices.upd(x+1, y);
    vertices.upd(x, y+1);
    vertices.upd(x+1, y+1);

    vertical.upd(x, y);
    vertical.upd(x, y+1);

    horizontal.upd(x, y);
    horizontal.upd(x+1, y);
}

void make_graph(int x, int y, char *moves){
    int pos = 0;
    while (true){
        add_block(x, y);

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

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

    vertices = bit(n+1, m+1);
    rivers = bit(n, m);
    vertical = bit(n, m+1);
    horizontal = bit(n+1, m);

    make_graph(sr, sc, moves);

    vertices.init();
    rivers.init();
    vertical.init();
    horizontal.init();
}

int colour(int ar, int ac, int br, int bc) {
    int v = vertices.query(ar+1, br, ac+1, bc); // + 2*(length+width)
    int e = vertical.query(ar, br, ac+1, bc); // + 2*length
    e += horizontal.query(ar+1, br, ac, bc); // + 2*width
    int r = rivers.query(ar, br, ac, bc);
    int c = (ar >= min_r || max_r >= br || ac >= min_c || max_c >= bc)?1:2;

    //printf("v = %d, e = %d, r = %d, c = %d\n", v, e, r, c);

    return e + c - v - r;
}

Compilation message

rainbow.cpp: In member function 'void bit::print(int)':
rainbow.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < vec[row].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23936 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 22 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 214 ms 31084 KB Output is correct
4 Correct 280 ms 32996 KB Output is correct
5 Correct 283 ms 32864 KB Output is correct
6 Correct 237 ms 32124 KB Output is correct
7 Correct 298 ms 32728 KB Output is correct
8 Correct 110 ms 31972 KB Output is correct
9 Correct 291 ms 32976 KB Output is correct
10 Correct 345 ms 32480 KB Output is correct
11 Correct 262 ms 32144 KB Output is correct
12 Correct 189 ms 32228 KB Output is correct
13 Correct 174 ms 32600 KB Output is correct
14 Correct 188 ms 32728 KB Output is correct
15 Correct 178 ms 32352 KB Output is correct
16 Correct 226 ms 31708 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Execution timed out 3077 ms 27856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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