oj.uz

Submission #262919

# Submission time Handle Problem Language Result Execution time Memory
262919 2020-08-13T11:07:14 Z evpipis Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 3000 ms 31580 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)?2:1;

    //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 28 ms 23928 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 21 ms 23856 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct
3 Correct 209 ms 29676 KB Output is correct
4 Correct 284 ms 31332 KB Output is correct
5 Correct 303 ms 31196 KB Output is correct
6 Correct 249 ms 30528 KB Output is correct
7 Correct 320 ms 31132 KB Output is correct
8 Correct 112 ms 30308 KB Output is correct
9 Correct 326 ms 31196 KB Output is correct
10 Correct 288 ms 30944 KB Output is correct
11 Correct 255 ms 30548 KB Output is correct
12 Correct 162 ms 30948 KB Output is correct
13 Correct 175 ms 31324 KB Output is correct
14 Correct 178 ms 31580 KB Output is correct
15 Correct 185 ms 31072 KB Output is correct
16 Correct 227 ms 30420 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Execution timed out 3089 ms 27864 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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