Algoogle

Algorithm for Programming Contest

PKU 2019 Cornfields

Category: PKU Tag: implementation

Cornfields

問題概要


解法


クエリ受けるたびに答え探すのでは明らかに間に合わないので前処理で答えを全て生成する.
一番左上から答えをだす.
mapでその範囲にある数の個数をもてばmapの始めと終わりの差で答えが出る.
ただし個数が0個になったやつは削除する.
これをBxBの左上を図のように移動させて見ていけば
毎回範囲外になる列(行)と範囲内になる列(行)だけ見ればいいので
2*Bの処理で答えが出せる.
pku2019-01

コード


(2019.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <map>

using namespace std;

int N, B, K;
int table[256][256];
int ans[256][256];

int main(){
    scanf("%d%d%d", &N, &B, &K);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            scanf("%d", &table[i][j]);

    map<int, int> cnt;
    for(int i = 0; i < B; i++)
        for(int j = 0; j < B; j++)
            cnt[table[i][j]]++;

    for(int i = 0; i < N-B+1; i++){
        if(i%2==0){
            for(int j = 0; j < N-B+1; j++){
                map<int,int>::iterator itr1 = cnt.end();
                map<int,int>::iterator itr2 = cnt.begin();
                ans[i][j] = ((--itr1)->first) - (itr2->first);
                if(j == N-B) continue;
                for(int ti = i; ti < i + B; ti++){
                    cnt[table[ti][j+B]]++;
                    cnt[table[ti][j]]--;
                    if(cnt[table[ti][j]] == 0)
                        cnt.erase(table[ti][j]);
                }
            }
            if(i == N - B) continue;
            for(int tj = N-B; tj < N; tj++){
                cnt[table[i+B][tj]]++;
                cnt[table[i][tj]]--;
                if(cnt[table[i][tj]] == 0)
                    cnt.erase(table[i][tj]);
            }
        }
        else{
            for(int j = N-B; j >= 0; j--){
                map<int,int>::iterator itr1 = cnt.end();
                map<int,int>::iterator itr2 = cnt.begin();
                ans[i][j] = ((--itr1)->first) - (itr2->first);
                if(j == 0) continue;
                for(int ti = i; ti < i + B; ti++){
                    cnt[table[ti][j-1]]++;
                    cnt[table[ti][j+B-1]]--;
                    if(cnt[table[ti][j+B-1]] == 0)
                        cnt.erase(table[ti][j+B-1]);
                }
            }
            if(i == N - B) continue;
            for(int tj = 0; tj < B; tj++){
                cnt[table[i+B][tj]]++;
                cnt[table[i][tj]]--;
                if(cnt[table[i][tj]] == 0)
                    cnt.erase(table[i][tj]);
            }
        }

    }

    while(K--){
        int i, j; scanf("%d%d", &i, &j);
        i--; j--;
        printf("%d\n", ans[i][j]);
    }
    /*
    for(int i = 0; i < N; i++){
        for(int j = 0; j< N; j++)
            printf("%d ", ans[i][j]);
        puts("");
    }
    */
    return 0;
}

Comments