結果
| 問題 |
No.2500 Products in a Range
|
| コンテスト | |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-10-13 23:54:57 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 19,515 bytes |
| コンパイル時間 | 3,424 ms |
| コンパイル使用メモリ | 101,836 KB |
| 実行使用メモリ | 493,992 KB |
| 最終ジャッジ日時 | 2024-09-15 19:47:48 |
| 合計ジャッジ時間 | 10,024 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 WA * 6 TLE * 1 -- * 52 |
ソースコード
import java.util.*;
import java.io.*;
import java.math.*;
import java.util.stream.*;
import java.util.function.*;
class Main implements Runnable
{
/*
* 最大パス長?
*/
void solve()
{
int N = in.nextInt() ;
long l = in.nextLong() , r = in.nextLong();
long [] A = in.LongArray(N);
Set<Integer> [] G = new HashSet[N];
int [] indegree = new int[N];
UnionFind uf = new UnionFind(N);
for(int i = 0 ; i < N ; i ++ )
{
G[i] = new HashSet<>();
for(int j = 0 ; j < N ; j ++ )
{
if(i == j) continue;
if(l <= (A[i] * A[j]) && (A[i] * A[j]) <= r)
{
G[i].add(j);
uf.unite(i, j);
}
}
}
List<List<Integer>> gp = uf.Groups();
int ans = 1 ;
for(List<Integer> p : gp)
{
for(int now : p)
{
int cnt = 0 ;
for(int nx : G[now])
{
if(G[nx].contains(now)) cnt ++ ;
}
if(p.size() - 1 >= cnt) ans = max(ans , cnt);
}
}
out.print(ans);
}
public static void main(String[] args)
{
new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
}
public void run()
{
solve();
out.flush();
}
record ip(int fi , int se) { public String toString() { return fi +" "+ se ;} }
record lp(long fi , long se) { public String toString() { return fi +" "+ se ;} }
public double dist(lp p1 , lp p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }
public int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }
public int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }
public long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }
public long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }
public int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}
public long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}
public int abs(int a , int b) { return (int) Math.abs(a - b) ; }
public long abs(long a , long b) { return (long) Math.abs(a - b) ; }
public int pow(int a , int b) { return (int) Math.pow(a , b) ; }
public long pow(long a , long b) { return (long) Math.pow(a , b) ; }
public long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }
public long [] recmod(int a , long MOD) { long [] recMod = new long[1 << 17] ; recMod[1] = 1 ; for(int i = 2 ; i < (1 << 17) ; i ++ ) recMod[i] = (recMod[i - 1] * i) % MOD9; return recMod; }
public int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }
public long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }
public int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }
public int lcm(int a, int b) { return a / gcd(a, b) * b; }
public long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }
public long lcm(long a, long b) { return a / gcd(a, b) * b; }
public int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }
public long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }
public int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }
public long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }
BigInteger cl(BigInteger... arr) { return Stream.of(arr).reduce((x, y) -> lcm(x, y)).orElse(BigInteger.ONE); }
BigInteger cg(BigInteger[] arr) { return Stream.of(arr).reduce(BigInteger::gcd).orElse(BigInteger.ZERO); }
BigInteger lcm(BigInteger x, BigInteger y) { return x.multiply(y).divide(Objects.nonNull(gcd(x, y)) ? gcd(x, y) : BigInteger.ONE); }
BigInteger gcd(BigInteger x, BigInteger y) { return (Objects.nonNull(x) ? x : BigInteger.ONE).gcd(y); }
public char upper(char c) { return (char)('A' + (c - 'a')); }
public char lower(char c) { return (char)('a' + (c - 'A')); }
public String yn(boolean a) { return a ? yes : no ; }
public String rev(String a) { return new StringBuilder(a).reverse().toString(); }
public void fill(int [] a , int v) { Arrays.fill(a , v); }
public void fill(long [] a , long v) { Arrays.fill(a , v); }
public void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }
public void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }
public void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }
public void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }
public int [] copy(int [] a) { return Arrays.copyOf(a , a.length); }
public long [] copy(long [] a) { return Arrays.copyOf(a , a.length); }
public String bin(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }
public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}
public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ; debug(c); fl();}
private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ; }
private void fl() { out.flush(); }
PrintWriter out = new PrintWriter(System.out);
In in = new In();
static final long MOD7 = 1000000007;
static final long MOD9 = 998244353;
static final int inf = (1 << 30);
static final long lnf = (1L << 60);
final String yes = "Yes";
final String no = "No" ;
final char [] dir = {'U','R','D','L'};
final int [] dy4 = {-1,0,1,0};
final int [] dx4 = {0,1,0,-1};
final int [] dy8 = {-1,-1,-1,0,1,1,1,0};
final int [] dx8 = {-1,0,1,1,1,0,-1,-1};
}
class UnionFind
{
private int [] rank , parents , size , data , edges;
private int groups ;
private BinaryOperator<Integer> op ;
private static BinaryOperator<Integer> def_op = (a, b) -> a;
UnionFind(int N) {
this(N , def_op);
}
UnionFind(int N , BinaryOperator<Integer> op)
{
this.rank = new int[N];
this.parents = new int[N];
this.size = new int[N];
this.data = new int[N];
this.edges = new int[N];
this.groups = N ;
for(int i = 0 ; i < N ; i ++ )
{
parents[i] = i ;
rank[i] = 0 ;
size[i] = 1 ;
data[i] = i ;
}
this.op = op ;
}
int Group() { return this.groups ; }
int Edge(int x) { return edges[root(x)] ; }
int Op(int x) { return data[root(x)] ; }
int Size(int x) { return size[root(x)] ; }
int root(int x)
{
if(x == parents[x]) return x ;
else parents[x] = root(parents[x]);
return parents[x];
}
boolean same(int x , int y) { return root(x) == root(y) ; }
void unite(int l , int r)
{
int left = root(l);
int right = root(r);
int parent = -1 , child = -1 ;
if(left == right) { ++ edges[right]; return ; }
parent = rank[left] > rank[right] ? left : right;
child = rank[left] > rank[right] ? right : left ;
--groups;
parents[child] = parent ;
rank[child] ++ ;
size[parent] += size[child] ;
edges[parent] += edges[child] + 1 ;
data[parent] = op.apply(data[child] , data[parent]);
}
List<List<Integer>> Groups() {
List<List<Integer>> Group = new ArrayList<>();
Map<Integer,List<Integer>> mp = new HashMap<>();
for(int i = 0 ; i < parents.length ; i ++ )
{
int par = root(i);
if(!mp.containsKey(par)) mp.put(par , new ArrayList<>());
mp.get(par).add(i);
}
for(List<Integer> lists : mp.values()) Group.add(new ArrayList<>(lists));
return Group;
}
}
class mint {
private long value;
private final long MOD;
public mint(long value, long MOD) {
this.MOD = MOD;
this.value = (value % MOD + MOD) % MOD;
}
public mint add(mint other) {
return new mint((this.value + other.value) % MOD, MOD);
}
public mint subtract(mint other) {
return new mint((this.value - other.value + MOD) % MOD, MOD);
}
public mint multiply(mint other) {
return new mint((this.value * other.value) % MOD, MOD);
}
public mint inverse() {
return new mint(pow(this.value, MOD - 2), MOD);
}
public mint divide(mint other) {
return this.multiply(other.inverse());
}
private long pow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) != 0) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
public long getVal() {
return value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
class SegmentTree
{
private int n ;
private long init ;
private long [] tree ;
private int size ;
private BinaryOperator<Long> op ;
SegmentTree(int size , long init , BinaryOperator<Long> op)
{
this.size = size;
this.init = init ;
this.op = op ;
n = 1 ;
while(n <= size) n *= 2 ;
this.tree = new long[2 * n];
for(int i = 0 ; i < 2 * n ; i ++ ) tree[i] = init ;
}
void update(int index , long value)
{
index += n ;
tree[index] = value ;
while(index > 0)
{
index /= 2 ;
tree[index] = op.apply(tree[2 * index] , tree[2 * index + 1]);
}
}
long query(int l , int r)
{
l += n ; r += n ;
long res = init ;
while(l < r)
{
if(l % 2 == 1){ res = op.apply(res , tree[l]) ; l ++ ; }
l /= 2 ;
if(r % 2 == 1){ res = op.apply(res , tree[r - 1]) ; r -- ; }
r /= 2 ;
}
return res ;
}
void debug()
{
for(int i = n ; i < n + size ; i ++ )
{
System.out.print(tree[i]+" ");
}
System.out.println();
}
}
class LazySegmentTree {
final long[] Dat;
final long[] Laz;
final int N;
final long E0;
final long E1;
final LongBinaryOperator F;
final LongBinaryOperator G;
final LongBinaryOperator H;
final LongBinaryOperator P;
final int[] Stack = new int[64];
//初期配列 , dat(関与しない値) , lazy(関与しない値) , dat() , dat&lazy() , lazy() , lazy*len()
public LazySegmentTree(int n, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {
this.E0 = e0;
this.E1 = e1;
this.F = f; this.G = g; this.H = h; this.P = p;
int k = 1;
while (k <= n) k <<= 1;
this.Dat = new long[k << 1];
this.Laz = new long[k << 1];
this.N = k;
Arrays.fill(Dat, E0);
Arrays.fill(Laz, E1);
}
public LazySegmentTree(long[] src, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {
this(src.length, e0, e1, f, g, h, p);
build(src);
}
private void build(long[] src) {
System.arraycopy(src, 0, Dat, N, src.length);
for (int i = N - 1; i > 0; i--) Dat[i] = F.applyAsLong(Dat[i << 1 | 0], Dat[i << 1 | 1]);
}
public void update(int l, int r, long v) {
if (l >= r) return;
int m = updown(l, r);
l += N; r += N;
for (; l < r; l >>= 1, r >>= 1) {
if ((l & 1) != 0) {Laz[l] = H.applyAsLong(Laz[l], v); l++;}
if ((r & 1) != 0) {r--; Laz[r] = H.applyAsLong(Laz[r], v);}
}
for (int i = 0; i < m; i++) {
int k = Stack[i];
Dat[k] = F.applyAsLong(calcDat(k << 1 | 0), calcDat(k << 1 | 1));
}
}
public long query(int i) {
int k = 1;
int l = 0, r = N;
while (k < N) {
int kl = k << 1 | 0;
int kr = k << 1 | 1;
Dat[k] = F.applyAsLong(calcDat(kl), calcDat(kr));
int m = (l + r) >> 1;
if (m > i) {r = m; k = kl;}
else {l = m; k = kr;}
}
return Dat[k];
}
public long query(int l, int r) {
if (l >= r) return E0;
updown(l, r);
long resL = E0, resR = E0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if ((l & 1) != 0) resL = F.applyAsLong(resL, calcDat(l++));
if ((r & 1) != 0) resR = F.applyAsLong(calcDat(--r), resR);
}
return F.applyAsLong(resL, resR);
}
private int updown(int l, int r) {
if (l >= r) return 0;
int i = 0;
int kl = l + N, kr = r + N;
for (int x = kl / (kl & -kl) >> 1, y = kr / (kr & -kr) >> 1; 0 < kl && kl < kr; kl >>= 1, kr >>= 1) {
if (kl <= x) Stack[i++] = kl;
if (kr <= y) Stack[i++] = kr;
}
for (; kl > 0; kl >>= 1) Stack[i++] = kl;
int m = i;
while (i > 0) calcDat(Stack[--i]);
return m;
}
private long calcDat(int k) {
long lz = Laz[k];
if (lz != E1) {
int w = N / Integer.highestOneBit(k);
Dat[k] = G.applyAsLong(Dat[k], P.applyAsLong(lz, w));
if (k < N) {
int l = k << 1 | 0, r = k << 1 | 1;
Laz[l] = H.applyAsLong(Laz[l], lz);
Laz[r] = H.applyAsLong(Laz[r], lz);
}
Laz[k] = E1;
}
return Dat[k];
}
void debug()
{
for(int i = Dat.length - N ; i < Dat.length - 1; i ++ )
{
System.out.print(Dat[i]+" ");
}
System.out.println();
}
}
class In
{
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++]; else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char nextChar() {
return next().charAt(0);
}
public int [] IntArray(int n) {
final int [] Array = new int [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextInt();
}
return Array;
}
public int [][] IntArray(int n , int m) {
final int [][] Array = new int [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = IntArray(m);
}
return Array;
}
public long [] LongArray(int n) {
final long [] Array = new long [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextLong();
}
return Array;
}
public long [][] LongArray(int n , int m) {
final long [][] Array = new long [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = LongArray(m);
}
return Array;
}
public String [] StringArray(int n) {
final String [] Array = new String [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next();
}
return Array;
}
public char [] CharArray(int n) {
final char [] Array = new char[n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().charAt(0);
}
return Array;
}
public char [][] CharArray(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().toCharArray();
}
return Array;
}
public char [][] CharArray2(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
for(int j = 0 ; j < m ; j ++ ) {
Array[i][j] = next().charAt(0);
}
}
return Array;
}
public List<Integer> [] Graph(int n) {
@SuppressWarnings("unchecked")
List<Integer> [] G = new ArrayList[n];
for(int i = 0 ; i < n ; i ++ ) {
G[i] = new ArrayList<>();
}
return G ;
}
}