Contest Duration: - (local time) (100 minutes) Back to Home

Submission #19339643

Source Code Expand

Copy
```import java.io.*;import java.util.*;import java.math.*;
public class Main
{
static long mod=1000000007l;
static int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;
static long maxl=Long.MAX_VALUE,minl=Long.MIN_VALUE;
static StringTokenizer st;
static StringBuilder sb;

static public void main(String[] args)throws Exception
{
int n=i();
long k=1l*i();
TreeMap<Integer,Long> h=new TreeMap<>();
for(int x=0;x<n;x++)
{
int a=i();
int b=i();
int c=i();
Long v=h.getOrDefault(a,0l);
v+=c;
h.put(a,v);

v=h.getOrDefault(b+1,0l);
v-=c;
h.put(b+1,v);
}
long c=0l;
int p=h.firstKey();
long pc=1l*h.get(p);
h.remove(p);
for(int e:h.keySet())
{
int d=e-p;
p=e;
long a=pc*d;
long b=k*d;
c+=min(a,b);
pc+=h.get(e);
}
pl(c);
}

static int[] so(int ar[])
{
Integer r[]=new Integer[ar.length];
for(int x=0;x<ar.length;x++)r[x]=ar[x];
Arrays.sort(r);
for(int x=0;x<ar.length;x++)ar[x]=r[x];
return ar;
}
static long[] so(long ar[])
{
Long r[]=new Long[ar.length];
for(int x=0;x<ar.length;x++)r[x]=ar[x];
Arrays.sort(r);
for(int x=0;x<ar.length;x++)ar[x]=r[x];
return ar;
}
static char[] so(char ar[])
{
Character r[]=new Character[ar.length];
for(int x=0;x<ar.length;x++)r[x]=ar[x];
Arrays.sort(r);
for(int x=0;x<ar.length;x++)ar[x]=r[x];
return ar;
}
static void s(String s){sb.append(s);}
static void s(int s){sb.append(s);}
static void s(long s){sb.append(s);}
static void s(char s){sb.append(s);}
static void s(double s){sb.append(s);}
static void ss(){sb.append(' ');}
static void sl(String s){sb.append(s);sb.append("\n");}
static void sl(int s){sb.append(s);sb.append("\n");}
static void sl(long s){sb.append(s);sb.append("\n");}
static void sl(char s){sb.append(s);sb.append("\n");}
static void sl(double s){sb.append(s);sb.append("\n");}
static void sl(){sb.append("\n");}
static int max(int ...a){int m=a[0];for(int e:a)m=(m>=e)?m:e;return m;}
static int min(int ...a){int m=a[0];for(int e:a)m=(m<=e)?m:e;return m;}
static int abs(int a){return Math.abs(a);}
static long max(long ...a){long m=a[0];for(long e:a)m=(m>=e)?m:e;return m;}
static long min(long ...a){long m=a[0];for(long e:a)m=(m<=e)?m:e;return m;}
static long abs(long a){return Math.abs(a);}
static int sq(int a){return (int)Math.sqrt(a);}
static long sq(long a){return (long)Math.sqrt(a);}
static long gcd(long a,long b){return b==0l?a:gcd(b,a%b);}
static boolean pa(String s,int i,int j)
{
while(i<j)if(s.charAt(i++)!=s.charAt(j--))return false;
return true;
}
static int ncr(int n,int c,long m)
{
long a=1l;
for(int x=n-c+1;x<=n;x++)a=((a*x)%m);
long b=1l;
for(int x=2;x<=c;x++)b=((b*x)%m);
return (int)((a*(mul((int)b,m-2,m)%m))%m);
}
static boolean[] si(int n)
{
boolean bo[]=new boolean[n+1];
bo[0]=true;bo[1]=true;
for(int x=4;x<=n;x+=2)bo[x]=true;
for(int x=3;x*x<=n;x+=2)
{
if(!bo[x])
{
int vv=(x<<1);
for(int y=x*x;y<=n;y+=vv)bo[y]=true;
}
}
return bo;
}
static int[] fac(int n)
{
int bo[]=new int[n+1];
for(int x=1;x<=n;x++)for(int y=x;y<=n;y+=x)bo[y]++;
return bo;
}
static long mul(long a,long b,long m)
{
long r=1l;
a%=m;
while(b>0)
{
if((b&1)==1)r=(r*a)%m;
b>>=1;
a=(a*a)%m;
}
return r;
}
static int i()throws IOException
{
return Integer.parseInt(st.nextToken());
}
static long l()throws IOException
{
return Long.parseLong(st.nextToken());
}
static String s()throws IOException
{
return st.nextToken();
}
static double d()throws IOException
{
return Double.parseDouble(st.nextToken());
}
static void p(Object p){System.out.print(p);}
static void p(String p){System.out.print(p);}
static void p(int p){System.out.print(p);}
static void p(double p){System.out.print(p);}
static void p(long p){System.out.print(p);}
static void p(char p){System.out.print(p);}
static void p(boolean p){System.out.print(p);}
static void pl(Object p){System.out.println(p);}
static void pl(String p){System.out.println(p);}
static void pl(int p){System.out.println(p);}
static void pl(char p){System.out.println(p);}
static void pl(double p){System.out.println(p);}
static void pl(long p){System.out.println(p);}
static void pl(boolean p){System.out.println(p);}
static void pl(){System.out.println();}
static void s(int a[])
{
for(int e:a)
{
sb.append(e);
sb.append(' ');
}
sb.append("\n");
}
static void s(long a[])
{
for(long e:a)
{
sb.append(e);
sb.append(' ');
}
sb.append("\n");
}
static void s(int ar[][])
{
for(int a[]:ar)
{
for(int e:a)
{
sb.append(e);
sb.append(' ');
}
sb.append("\n");
}
}
static void s(char a[])
{
for(char e:a)
{
sb.append(e);
sb.append(' ');
}
sb.append("\n");
}
static void s(char ar[][])
{
for(char a[]:ar)
{
for(char e:a)
{
sb.append(e);
sb.append(' ');
}
sb.append("\n");
}
}
static int[] ari(int n)throws IOException
{
int ar[]=new int[n];
for(int x=0;x<n;x++)ar[x]=Integer.parseInt(st.nextToken());
return ar;
}
static int[][] ari(int n,int m)throws IOException
{
int ar[][]=new int[n][m];
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)ar[x][y]=Integer.parseInt(st.nextToken());
}
return ar;
}
static long[] arl(int n)throws IOException
{
long ar[]=new long[n];
for(int x=0;x<n;x++) ar[x]=Long.parseLong(st.nextToken());
return ar;
}
static long[][] arl(int n,int m)throws IOException
{
long ar[][]=new long[n][m];
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)ar[x][y]=Long.parseLong(st.nextToken());
}
return ar;
}
static String[] ars(int n)throws IOException
{
String ar[]=new String[n];
for(int x=0;x<n;x++) ar[x]=st.nextToken();
return ar;
}
static double[] ard(int n)throws IOException
{
double ar[]=new double[n];
for(int x=0;x<n;x++)ar[x]=Double.parseDouble(st.nextToken());
return ar;
}
static double[][] ard(int n,int m)throws IOException
{
double ar[][]=new double[n][m];
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)ar[x][y]=Double.parseDouble(st.nextToken());
}
return ar;
}
static char[] arc(int n)throws IOException
{
char ar[]=new char[n];
for(int x=0;x<n;x++)ar[x]=st.nextToken().charAt(0);
return ar;
}
static char[][] arc(int n,int m)throws IOException
{
char ar[][]=new char[n][m];
for(int x=0;x<n;x++)
{
for(int y=0;y<m;y++)ar[x][y]=s.charAt(y);
}
return ar;
}
static void p(int ar[])
{
StringBuilder sb=new StringBuilder(2*ar.length);
for(int a:ar)
{
sb.append(a);
sb.append(' ');
}
System.out.println(sb);
}
static void p(int ar[][])
{
StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
for(int a[]:ar)
{
for(int aa:a)
{
sb.append(aa);
sb.append(' ');
}
sb.append("\n");
}
p(sb);
}
static void p(long ar[])
{
StringBuilder sb=new StringBuilder(2*ar.length);
for(long a:ar)
{
sb.append(a);
sb.append(' ');
}
System.out.println(sb);
}
static void p(long ar[][])
{
StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
for(long a[]:ar)
{
for(long aa:a)
{
sb.append(aa);
sb.append(' ');
}
sb.append("\n");
}
p(sb);
}
static void p(String ar[])
{
int c=0;
for(String s:ar)c+=s.length()+1;
StringBuilder sb=new StringBuilder(c);
for(String a:ar)
{
sb.append(a);
sb.append(' ');
}
System.out.println(sb);
}
static void p(double ar[])
{
StringBuilder sb=new StringBuilder(2*ar.length);
for(double a:ar)
{
sb.append(a);
sb.append(' ');
}
System.out.println(sb);
}
static void p(double ar[][])
{
StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
for(double a[]:ar)
{
for(double aa:a)
{
sb.append(aa);
sb.append(' ');
}
sb.append("\n");
}
p(sb);
}
static void p(char ar[])
{
StringBuilder sb=new StringBuilder(2*ar.length);
for(char aa:ar)
{
sb.append(aa);
sb.append(' ');
}
System.out.println(sb);
}
static void p(char ar[][])
{
StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
for(char a[]:ar)
{
for(char aa:a)
{
sb.append(aa);
sb.append(' ');
}
sb.append("\n");
}
p(sb);
}
}```

#### Submission Info

Submission Time 2021-01-10 21:44:10+0900 D - Snuke Prime Aabhas99 Java (OpenJDK 1.8.0) 0 11343 Byte WA 1097 ms 80188 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
 AC × 3
 AC × 27 WA × 1
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 82 ms 25332 KB
random_02.txt AC 70 ms 25192 KB
random_03.txt AC 71 ms 25424 KB
random_04.txt AC 74 ms 25528 KB
random_05.txt AC 74 ms 25356 KB
random_06.txt AC 77 ms 25468 KB
random_07.txt AC 74 ms 25360 KB
random_08.txt AC 81 ms 25144 KB
random_09.txt AC 76 ms 25544 KB
random_10.txt AC 80 ms 25192 KB
random_11.txt AC 72 ms 25264 KB
random_12.txt AC 73 ms 25480 KB
random_13.txt AC 74 ms 25360 KB
random_14.txt AC 70 ms 25264 KB
random_15.txt AC 75 ms 25468 KB
random_16.txt AC 399 ms 50672 KB
random_17.txt AC 679 ms 65900 KB
random_18.txt AC 542 ms 62008 KB
random_19.txt AC 574 ms 61336 KB
random_20.txt AC 1071 ms 79052 KB
random_21.txt AC 827 ms 70280 KB
random_22.txt AC 258 ms 40292 KB
random_23.txt AC 1085 ms 80188 KB
random_24.txt AC 1097 ms 79812 KB
random_25.txt WA 302 ms 45916 KB
sample_01.txt AC 77 ms 25328 KB
sample_02.txt AC 71 ms 25364 KB
sample_03.txt AC 73 ms 25500 KB