Submission #951897
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;
}
}
FenwickE() {}
/*
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<FenwickE<T>> seg;
Fenwick2D(int N, int M) : N(N) {
seg.resize(N);
for (int i = 0; i < N; i++) {
seg[i] = FenwickE<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 |
0 |
Code Size |
4139 Byte |
Status |
MLE |
Exec Time |
5055 ms |
Memory |
314660 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 |
0 / 100 |
Status |
|
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 |
MLE |
479 ms |
313460 KB |
00-sample-01 |
MLE |
458 ms |
313500 KB |
10-random_small-00 |
MLE |
534 ms |
313504 KB |
10-random_small-01 |
MLE |
462 ms |
313504 KB |
10-random_small-02 |
MLE |
667 ms |
313496 KB |
10-random_small-03 |
MLE |
466 ms |
313496 KB |
10-random_small-04 |
MLE |
593 ms |
313500 KB |
10-random_small-05 |
MLE |
1897 ms |
313508 KB |
10-random_small-06 |
MLE |
465 ms |
313716 KB |
10-random_small-07 |
MLE |
557 ms |
313628 KB |
10-random_small-08 |
MLE |
516 ms |
313632 KB |
20-random_large-00 |
TLE |
5047 ms |
314604 KB |
20-random_large-01 |
TLE |
5052 ms |
314660 KB |
20-random_large-02 |
TLE |
5045 ms |
314536 KB |
20-random_large-03 |
TLE |
5048 ms |
314592 KB |
20-random_large-04 |
TLE |
5048 ms |
314652 KB |
30-max_query-00 |
TLE |
5055 ms |
314656 KB |
30-max_query-01 |
TLE |
5046 ms |
314660 KB |
30-max_query-02 |
TLE |
5048 ms |
314604 KB |