Submission #1000593
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
typedef long double ld;
typedef long long ll;
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif
#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"
const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);
void precalc() {
}
const int maxn = (int) 2e5 + 10;
int n;
int a[maxn], b[maxn];
int read() {
if (scanf("%d", &n) < 1) {
return 0;
}
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", b + i);
}
return 1;
}
const int mod = (int) 1e9 + 7;
int mult(int x, int y) {
return (long long) x * y % mod;
}
int xs[maxn];
struct ftree {
int n;
int a[maxn];
void build(int _n) {
n = _n;
for (int i = 0; i < n; ++i) {
a[i] = 0;
}
}
void add(int x, int toadd) {
for (; x < n; x |= (x + 1)) {
a[x] += toadd;
}
}
int get(int x) {
int res = 0;
for (; x >= 0; x = (x & (x + 1)) - 1) {
res += a[x];
}
return res;
}
} tree;
void solve() {
sort(a, a + n);
sort(b, b + n);
merge(a, a + n, b, b + n, xs);
tree.build(2 * n);
int res = 1;
for (int i = 0; i < n; ++i) {
int pos1 = lower_bound(xs, xs + 2 * n, a[i]) - xs;
int pos2 = lower_bound(xs, xs + 2 * n, b[i]) - xs;
if (pos1 > pos2) {
swap(pos1, pos2);
}
res = mult(res, tree.get(pos2) - tree.get(pos1) + 1);
tree.add(pos1, 1);
tree.add(pos2, 1);
}
printf("%d\n", res);
}
int main() {
precalc();
#ifdef LOCAL
freopen(TASK ".out", "w", stdout);
assert(freopen(TASK ".in", "r", stdin));
#endif
while (1) {
if (!read()) {
break;
}
solve();
#ifdef DEBUG
eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time
2016-11-28 12:08:46+0900
Task
A - 1D Matching
User
XraY
Language
C++14 (GCC 5.4.1)
Score
500
Code Size
2138 Byte
Status
AC
Exec Time
58 ms
Memory
2560 KB
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:46:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
^
./Main.cpp:49:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", b + i);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
500 / 500
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
AC
36 ms
1664 KB
001.txt
AC
14 ms
768 KB
002.txt
AC
19 ms
1024 KB
003.txt
AC
21 ms
1024 KB
004.txt
AC
52 ms
2304 KB
005.txt
AC
58 ms
2560 KB
006.txt
AC
58 ms
2560 KB
007.txt
AC
58 ms
2560 KB
008.txt
AC
58 ms
2560 KB
009.txt
AC
58 ms
2560 KB
010.txt
AC
57 ms
2560 KB
011.txt
AC
57 ms
2560 KB
example0.txt
AC
3 ms
256 KB
example1.txt
AC
3 ms
256 KB