結果

問題 No.989 N×Mマス計算(K以上)
ユーザー LayCurse
提出日時 2020-02-14 21:28:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 5,406 bytes
コンパイル時間 2,850 ms
コンパイル使用メモリ 222,460 KB
最終ジャッジ日時 2025-01-09 00:02:09
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
void sortF_L(int N, unsigned A[], void *mem = wmem){
int i;
int m;
int bt;
unsigned *arr;
unsigned c;
int *sz;
if(N < 256){
sort(A, A+N);
return;
}
bt = sizeof(unsigned) * 8;
walloc1d(&arr, N, &mem);
walloc1d(&sz, N, &mem);
for(m=0;m<bt;m+=8){
for(i=(0);i<(257);i++){
sz[i] = 0;
}
for(i=(0);i<(N);i++){
sz[ 1+((A[i]>>m)&255u) ]++;
}
for(i=(1);i<(257);i++){
sz[i] += sz[i-1];
}
for(i=(0);i<(N);i++){
c = ((A[i]>>m)&255u);
arr[sz[c]++] = A[i];
}
swap(A, arr);
}
}
void sortF_L(int N, int A[], void *mem = wmem){
int i;
int x;
int y;
int z;
int *arr;
unsigned *send;
if(N < 256){
sort(A, A+N);
return;
}
send = (unsigned*)A;
sortF_L(N, send, mem);
if(A[0] < 0 || A[N-1] >= 0){
return;
}
x = 0;
y = N;
while(x < y){
z = (x+y) / 2;
if(A[z] < 0){
y = z;
}
else{
x = z+1;
}
}
walloc1d(&arr, N, &mem);
z = 0;
for(i=(x);i<(N);i++){
arr[z++] = A[i];
}
for(i=(0);i<(x);i++){
arr[z++] = A[i];
}
for(i=(0);i<(N);i++){
A[i] = arr[i];
}
}
void sortF_L(int N, unsigned long long A[], void *mem = wmem){
int i;
int m;
int bt;
unsigned long long *arr;
unsigned c;
int *sz;
if(N < 512){
sort(A, A+N);
return;
}
bt = sizeof(unsigned long long) * 8;
walloc1d(&arr, N, &mem);
walloc1d(&sz, N, &mem);
for(m=0;m<bt;m+=8){
for(i=(0);i<(257);i++){
sz[i] = 0;
}
for(i=(0);i<(N);i++){
sz[ 1+((A[i]>>m)&255u) ]++;
}
for(i=(1);i<(257);i++){
sz[i] += sz[i-1];
}
for(i=(0);i<(N);i++){
c = ((A[i]>>m)&255u);
arr[sz[c]++] = A[i];
}
swap(A, arr);
}
}
void sortF_L(int N, long long A[], void *mem = wmem){
int i;
int x;
int y;
int z;
long long *arr;
unsigned long long *send;
if(N < 512){
sort(A, A+N);
return;
}
send = (unsigned long long*)A;
sortF_L(N, send, mem);
if(A[0] < 0 || A[N-1] >= 0){
return;
}
x = 0;
y = N;
while(x < y){
z = (x+y) / 2;
if(A[z] < 0){
y = z;
}
else{
x = z+1;
}
}
walloc1d(&arr, N, &mem);
z = 0;
for(i=(x);i<(N);i++){
arr[z++] = A[i];
}
for(i=(0);i<(x);i++){
arr[z++] = A[i];
}
for(i=(0);i<(N);i++){
A[i] = arr[i];
}
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline void rd(long long &x){
int k;
int m=0;
x=0;
for(;;){
k = getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline void rd(char &c){
int i;
for(;;){
i = getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c = i;
}
inline int rd(char c[]){
int i;
int sz = 0;
for(;;){
i = getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c[sz++] = i;
for(;;){
i = getchar_unlocked();
if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
break;
}
c[sz++] = i;
}
c[sz]='\0';
return sz;
}
inline void wt_L(char a){
putchar_unlocked(a);
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
putchar_unlocked('-');
}
while(s--){
putchar_unlocked(f[s]+'0');
}
}
int N;
int M;
int K;
long long A[100000];
long long B[100000];
char op;
int main(){
wmem = memarr;
int i;
int j;
int k;
long long res = 0;
rd(N);
rd(M);
rd(K);
rd(op);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(M);Lj4PdHRW++){
rd(B[Lj4PdHRW]);
}
}
{
int e98WHCEY;
for(e98WHCEY=(0);e98WHCEY<(N);e98WHCEY++){
rd(A[e98WHCEY]);
}
}
sortF_L(N, A);
sortF_L(M, B);
if(op=='+'){
j = 0;
for(i=(N)-1;i>=(0);i--){
while(j < M && A[i] + B[j] < K){
j++;
}
res += M - j;
}
}
else{
j = 0;
for(i=(N)-1;i>=(0);i--){
while(j < M && A[i] * B[j] < K){
j++;
}
res += M - j;
}
}
wt_L(res);
wt_L('\n');
return 0;
}
// cLay varsion 20200214-1
// --- original code ---
// int N, M, K; ll A[1d5], B[1d5];
// char op;
// {
// int i, j, k;
// ll res = 0;
// rd(N,M,K,op,B(M),A(N));
// sortF(N, A);
// sortF(M, B);
// if(op=='+'){
// j = 0;
// rrep(i,N){
// while(j < M && A[i] + B[j] < K) j++;
// res += M - j;
// }
// } else {
// j = 0;
// rrep(i,N){
// while(j < M && A[i] * B[j] < K) j++;
// res += M - j;
// }
// }
// wt(res);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0