Hello Everyone, today I tried to solve the problem Subsegment xor sum during the mock ICPC-2020 contest. But to my surprise, my java code didn’t pass and showed MLE. However the same code got accepted when was submitted in cpp by translating my java code. I also faced this issue many times during practicing in codedrills.
However, when i removed my fast-IO of my java, it showed TLE verdict on the same-testset, Test-Set 2. I am pretty sure ther might be a problem on the Codedrills java-compiler. Anybody who solved the problem using JAVA, please share your views or your accepted code. I don’t know why is this issue arising as my fast-IO code gets passed on different competitive websites.
@admins pls look into this matter as we might end up getting penalty due to this problem or issue. My codes always get MLE, in Codedrills however the same-logic cpp codes get passed.
I am hereby attaching my codes and verdicts received from Codedrills.
JAVA Code
import java.io.*;
import java.util.*;
import java.util.StringTokenizer;
class Main {
static long mod = (long) 1e9+7;
public static void main(String[] args) throws IOException {
Soumit sc = new Soumit();
int t = sc.nextInt();
StringBuilder sb = new StringBuilder();
while (t-->0){
int n = sc.nextInt();
long[] arr = sc.nextLongArray(n);
long[][] ans = new long[31][n];
long[][] dp = new long[31][n];
for(int i=0;i<n;i++){
for(int j=0;j<ans.length;j++){
ans[j][i] = (arr[i]&(1L<<j))==0?0:1;
}
}
/*for(long[] i: ans){
System.out.println(Arrays.toString(i));
}
System.out.println();*/
for(int i=0;i<dp.length;i++){
long last = 0;
for(int j=0;j<n;j++){
if(ans[i][j]==1){
last = j-last+1;
}
dp[i][j] = last;
}
//System.out.println(Arrays.toString(dp[i]));
for(int j=1;j<n;j++){
dp[i][j] = (dp[i][j]+dp[i][j-1])%mod;
}
}
/*System.out.println();
for(long[] i: dp){
System.out.println(Arrays.toString(i));
}*/
long sum = 0;
for(int i=0;i<dp.length;i++){
sum = (sum + (dp[i][n-1] * ((1L<<i)%mod)) %mod) %mod;
}
sb.append(sum).append("\n");
}
System.out.println(sb);
sc.close();
}
static class Soumit {
final private int BUFFER_SIZE = 1 << 18;
final private DataInputStream din;
final private byte[] buffer;
private PrintWriter pw;
private int bufferPointer, bytesRead;
StringTokenizer st;
public Soumit() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Soumit(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public void streamOutput(String file) throws IOException {
FileWriter fw = new FileWriter(file);
BufferedWriter bw = new BufferedWriter(fw);
pw = new PrintWriter(bw);
}
public void println(String a) {
pw.println(a);
}
public void print(String a) {
pw.print(a);
}
public String readLine() throws IOException {
byte[] buf = new byte[3000064]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public void sort(int[] arr) {
ArrayList<Integer> arlist = new ArrayList<>();
for (int i : arr)
arlist.add(i);
Collections.sort(arlist);
for (int i = 0; i < arr.length; i++)
arr[i] = arlist.get(i);
}
public void sort(long[] arr) {
ArrayList<Long> arlist = new ArrayList<>();
for (long i : arr)
arlist.add(i);
Collections.sort(arlist);
for (int i = 0; i < arr.length; i++)
arr[i] = arlist.get(i);
}
public int[] nextIntArray(int n) throws IOException {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = nextInt();
}
return arr;
}
public long[] nextLongArray(int n) throws IOException {
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = nextLong();
}
return arr;
}
public double[] nextDoubleArray(int n) throws IOException {
double[] arr = new double[n];
for (int i = 0; i < n; i++) {
arr[i] = nextDouble();
}
return arr;
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
/*if (din == null)
return;*/
if (din != null) din.close();
if (pw != null) pw.close();
}
}
}
CPP code
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define s second
#define f first
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vl vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define mii unordered_map<int,int>
#define mod 1000000007
#define nextline cout<<"\n"
int gcd(int a,int b)
{
if(b == 0)
return a;
return gcd(b , a % b);
}
int lcm (int a,int b)
{
return (a*b)/(gcd(a,b));
}
bool isPowerOfTwo(ll n)
{
if (n == 0)
return 0;
while (n != 1)
{
if (n%2 != 0)
return 0;
n = n/2;
}
return 1;
}
ll power(ll x, ll n, ll p) {
ll res = 1;
if(n == 0) return 1;
if(n == 1) return x%p;
if(n%2 == 1) res = x%p;
ll temp = power(x,n/2,p);
return res*((temp*temp)%p)%p;
}
bool compare(pair<ll,ll> a,pair<ll,ll> b)
{
if(a.f != b.f)
return a.f<b.f;
else return (a.s<b.s);
}
void solve(){
ll b,c,n;
cin>>n;
ll a[n];
for (int i = 0; i < n; ++i)
{
cin>>a[i];
}
ll ans[31][n];
ll dp[31][n];
for (int i = 0; i < n; ++i)
{
for(int j = 0; j < 31; j++)
{
ans[j][i] = (a[i]&(1L<<j))==0?0:1;
}
}
for(int i=0;i<31;i++)
{
ll last = 0;
for(int j=0;j<n;j++)
{
if(ans[i][j]==1)
{
last = j-last+1;
}
dp[i][j] = last;
}
for(int j=1;j<n;j++)
{
dp[i][j] = (dp[i][j]+dp[i][j-1])%mod;
}
}
ll sum = 0;
for(int i=0;i<31;i++)
{
sum = (sum + (dp[i][n-1] * ((1L<<i)%mod)) %mod) %mod;
}
cout<<sum<<"\n";
}
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
cin>>t;
//t = 1;
while(t--)
{
solve();
}
return 0;
}
Please help me. Thanks in advance