Submission #951893


Source Code Expand

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <random>
#include <cassert>
#include <ctime>
#include <array>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

int bsr(int x) { return 31 - __builtin_clz(x); }

const int X = 5;
/**
 * Fenwick Tree(0-indexed)
 */
template<class T>
struct FenwickE {
    int N;
    using P = array<T, 2>;
    vector<P> seg[X];
    FenwickE(int N) : N(N) {
//        seg.resize(X);
        N = (N+3)/4*4;
        for (int i = 0; i < X; i++) {
            seg[i] = vector<P>(N+4, P{T{0}, T{0}});
            N = (N+3)/4;
            N = (N+3)/4*4;
            cout << seg[i].size() << endl;
        }
    }
    /*
     add:
        01 1 23 3
           0    2
     sum:

        0  1 2  3
        23
        01
     */
    /// i番目の要素にxを追加する
    void add(int p, T x) {
        for (int i = 0; i < X; i++) {
            seg[i][p|1][p&1] += x;
            seg[i][p&~1][1] += x;
            p >>= 2;
        }
    }
    /// [0, i)のsum
    T sum(int p) {
        T s{0};
        for (int i = 0; i < X; i++) {
            s += seg[i][p][0];
            s += seg[i][p&~3][(p&2)>>1];
            p >>= 2;
        }
        return s;
    }
    /// [a, b)のsum
    T sum(int a, int b) {
        return sum(b) - sum(a);
    }
};

/**
 * Fenwick Tree 
 *
 * 0-indexed
 */
template<class T>
struct Fenwick {
    int N;
    vector<T> seg;
    Fenwick(int N) : N(N) {
        seg.resize(N);
        fill_n(begin(seg), N, 0);
    }
    Fenwick() {}
    /// i番目の要素にxを追加する
    void add(int i, T x) {
        while (i < N) {
            seg[i] += x;
            i |= i+1;
        }
    }
    /// [0, i)のsum
    T sum(int i) {
        T s{0};
        while (i > 0) {
            s += seg[i-1];
            i -= i & -i;
        }
        return s;
    }
    /// [a, b)のsum
    T sum(int a, int b) {
        return sum(b) - sum(a);
    }
};

/**
 * Fenwick Tree 
 *
 * 0-indexed
 */
template<class T>
struct Fenwick2D {
    int N;
    vector<Fenwick<T>> seg;
    Fenwick2D(int N, int M) : N(N) {
        seg.resize(N);
        for (int i = 0; i < N; i++) {
            seg[i] = Fenwick<T>(M);
        }
    }
    Fenwick2D() {}
    /// i番目の要素にxを追加する
    void add(int i, int j, T x) {
        while (i < N) {
            seg[i].add(j, x);
            i |= i+1;
        }
    }
    /// [0, i)のsum
    T sum(int i, int j) {
        T s{0};
        while (i > 0) {
            s += seg[i-1].sum(j);
            i -= i & -i;
        }
        return s;
    }
    /// [a, b)のsum
    T sum(int a, int b, int c, int d) {
        return sum(c, d) - sum(a, d) - sum(c, b) + sum(a, b);
    }
};

Fenwick2D<int> fw[110];
int bo[520][520];

int main() {
    for (int i = 0; i < 110; i++) {
        fw[i] = Fenwick2D<int>(504, 504);
    }
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            scanf("%d", &x); x--;
            bo[i][j] = x;
            fw[x].add(i, j, 1);
        }
    }

    int q;
    scanf("%d", &q);
    for (int un = 0; un < q; un++) {
        int ty;
        int a, b, c, d;
        scanf("%d %d %d %d %d", &ty, &a, &b, &c, &d);
        if (ty == 1) {
            a--; b--; c--; d--;
            int x = bo[a][b], y = bo[c][d];
            fw[x].add(a, b, -1);
            fw[x].add(c, d, 1);
            fw[y].add(a, b, 1);
            fw[y].add(c, d, -1);
            swap(bo[a][b], bo[c][d]);
        } else {
            a--; b--;
            int md = -1, mk = -1;
            for (int i = 0; i < k; i++) {
                int x = fw[i].sum(a, b, c, d);
                if (md <= x) {
                    md = x;
                    mk = i;
                }
            }
            printf("%d %d\n", mk+1, md);
        }
    }
    return 0;
}

Submission Info

Submission Time
Task C - 宝探し 2
User yosupo
Language C++11 (GCC 4.8.1)
Score 100
Code Size 4162 Byte
Status AC
Exec Time 4496 ms
Memory 113448 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:152:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
                                  ^
./Main.cpp:156:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x); x--;
                            ^
./Main.cpp:163:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
                    ^
./Main.cpp:167:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d %d", &ty, &a, &b, &c, &d);
                                                     ^

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 19
Set Name Test Cases
All 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 30-max_query-00, 30-max_query-01, 30-max_query-02
Case Name Status Exec Time Memory
00-sample-00 AC 189 ms 112500 KB
00-sample-01 AC 190 ms 112544 KB
10-random_small-00 AC 250 ms 112504 KB
10-random_small-01 AC 192 ms 112544 KB
10-random_small-02 AC 243 ms 112548 KB
10-random_small-03 AC 192 ms 112628 KB
10-random_small-04 AC 273 ms 112628 KB
10-random_small-05 AC 678 ms 112548 KB
10-random_small-06 AC 197 ms 112628 KB
10-random_small-07 AC 243 ms 112660 KB
10-random_small-08 AC 210 ms 112620 KB
20-random_large-00 AC 2460 ms 113444 KB
20-random_large-01 AC 2460 ms 113444 KB
20-random_large-02 AC 2462 ms 113440 KB
20-random_large-03 AC 2495 ms 113440 KB
20-random_large-04 AC 2469 ms 113444 KB
30-max_query-00 AC 4292 ms 113444 KB
30-max_query-01 AC 4496 ms 113436 KB
30-max_query-02 AC 4366 ms 113448 KB