CLKLZM_tester.java

import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

class FirstThingFirst  
{
    static IO5 io=new IO5(System.in);
    static LinkedList<Beam>[] toAdd;
    static int n, m;
    static long[] health;
    
    static Comparator<Beam> com = new Comparator<Beam>()
    {
        public int compare(Beam a, Beam b)
        {
            return Integer.compare(b.r, a.r);
        }
    };
    
    public static void main(String[] args)throws Exception
    {
        int i;
        for(int tc=io.nextInt();tc>0;--tc)
        {
            health = new long[n = io.nextInt()];
            m = io.nextInt();
            
            toAdd = new LinkedList[n];
            for(i=0; i<n; ++i)
            {
                health[i] = io.nextLong();
                toAdd[i] = new LinkedList<>();
            }
            for(i=0; i<m; ++i)
            {
                Beam intro = new Beam(io.nextInt()-1, io.nextInt()-1, io.nextInt());
                toAdd[intro.l].add(intro);
            }
            
            PriorityQueue<Beam> avl = new PriorityQueue<>(com);
            long[] damageStatus = new long[n];
            long currDamage = 0, ans = 0;
            
            for(i=0; i<n; ++i)
            {
                avl.addAll(toAdd[i]);
                health[i] -= currDamage;
                while(health[i] > 0 && avl.size() > 0)
                {
                    Beam longest = avl.peek();
                    if(longest.r < i)   break;
                    if(longest.max > health[i])
                    {
                        longest.max -= health[i];
                        currDamage += health[i];
                        damageStatus[longest.r] -= health[i];
                        ans += health[i];
                        health[i] = 0;
                    }
                    else
                    {
                        avl.poll();
                        currDamage += longest.max;
                        damageStatus[longest.r] -= longest.max;
                        ans += longest.max;
                        health[i] -= longest.max;
                    }
                }
                if(health[i] > 0)break;
                currDamage += damageStatus[i];
            }
            io.println(i>=n? "YES "+ans : "NO");
        }
        io.flush();
    }
}
class Beam
{
    int l, r, max;
    Beam(int a, int b, int c){l = a;    r = b;  max = c;}
    String getString(){return "("+l+", "+r+" -> "+max+")";}
}
class IO5
{
    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static StringBuilder sb = new StringBuilder();
    
 
    IO5(InputStream is)
    {
        in = is;
    }
 
    int scan() throws Exception
    {
        if(index>=total){
            index = 0;
            total = in.read(buf);
            if(total<=0)
                return -1;
        }
        return buf[index++];
    }
 
    String next() throws Exception
    {
        int c;
        for(c=scan(); c<=32; c=scan());
        StringBuilder sb = new StringBuilder();
        for(; c>32; c=scan())
            sb.append((char)c);
        return sb.toString();
    }
 
    int nextInt() throws Exception
    {
        int c, val = 0;
        for(c=scan(); c<=32; c=scan());
        boolean neg = c=='-';
        if(c=='-' || c=='+')
            c = scan();
        for(; c>='0' && c<='9'; c=scan())
            val = (val<<3) + (val<<1) + (c&15);
        return neg?-val:val;
    }
    long nextLong() throws Exception
    {
        int c;long val = 0;
        for(c=scan(); c<=32; c=scan());
        boolean neg = c=='-';
        if(c=='-' || c=='+')
            c = scan();
        for(; c>='0' && c<='9'; c=scan())
            val = (val<<3) + (val<<1) + (c&15);
        return neg?-val:val;
    }
    void print(Object a)
    {
        sb.append(a.toString());
    }
    void println(Object a)
    {
        sb.append(a.toString()).append("\n");
    }
    void println()
    {
        sb.append("\n");
    }
    void flush()
    {
        System.out.print(sb);
        sb = new StringBuilder();
    }
}