Submission #1174275


Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    public Solve(){}
    int N;
    long[] DPL;
    long[] DPR;
    long[] unuse;
    long[] use;
    long[] sumL;
    long[] sumR;
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        long[] T = new long[N];
        for(int i=0;i<N;i++){
            T[i] = int.Parse(str[i]);
        }
        DPL = new long[N];
        DPR = new long[N];
        {
            sumL = new long[N];
            sumL[0] = T[0];
            for(int i=1;i<N;i++){
                sumL[i] = sumL[i-1] + T[i];
            }
            ConvexHullTrick Con = new ConvexHullTrick(N);
            Con.Add(-1,1);
            for(int i=0;i<N;i++){
                DPL[i] = Math.Max(i == 0 ? 0 : DPL[i-1],Con.Query(-i)-sumL[i]+i*(i+1)/2);
                Con.Add(i,DPL[i]+sumL[i]+i*(i-1)/2);
            }
        }
        {
            sumR = new long[N];
            sumR[0] = T[N-1];
            for(int i=1;i<N;i++){
                sumR[i] = sumR[i-1] + T[N-1-i];
            }
            ConvexHullTrick Con = new ConvexHullTrick(N);
            Con.Add(-1,1);
            for(int i=0;i<N;i++){
                DPR[N-1-i] = Math.Max(i == 0 ? 0 : DPR[N-i],Con.Query(-i)-sumR[i]+i*(i+1)/2);
                Con.Add(i,DPR[N-1-i]+sumR[i]+i*(i-1)/2);
            }
        }
        unuse = new long[N];
        for(int i=0;i<N;i++){
            unuse[i] = (i == 0 ? 0 : DPL[i-1]) + (i == N-1 ? 0 : DPR[i+1]);
        } 
        use = new long[N];
        for(int i=0;i<N;i++){
            use[i] = -T[i];
        }
        GetUse(0,N-1);
        int M = int.Parse(Console.ReadLine());
        for(int i=0;i<M;i++){
            str = Console.ReadLine().Split(' ');
            int P = int.Parse(str[0])-1;
            long X = int.Parse(str[1]);
            sb.Append(Math.Max(unuse[P],use[P]-X+T[P])+"\n");
        }
    }
    ConvexHullTrick ConL(int l,int r){
        ConvexHullTrick Con = new ConvexHullTrick(r-l+1);
        for(int i=l;i<=r;i++){
            if(i == 0){
                Con.Add(-1,1);
            }
            else{
                Con.Add(i-1,DPL[i-1]+sumL[i-1]+(i-1)*(i-2)/2);
            }
        }
        return Con;
    }
    ConvexHullTrick ConR(int l,int r){
        ConvexHullTrick Con = new ConvexHullTrick(r-l+1);
        for(int i=N-1-r;i<N-l;i++){
            if(i == 0){
                Con.Add(-1,1);
            }
            else{
                Con.Add(i-1,DPR[N-i]+sumR[i-1]+(i-1)*(i-2)/2);
            }
        }
        return Con;
    }
    long UseConL(int i){
        return -sumL[i]+i*(i+1)/2;
    }
    long UseConR(int i){
        return -sumR[N-1-i]+(N-1-i)*(N-i)/2;
    }
    void GetUse(int l,int r){
        int M = (l+r)/2;
        if(l <= M-1){
            GetUse(l,M-1);
        }
        if(M+1 <= r){
            GetUse(M+1,r);
        }
        {
            ConvexHullTrick Con = ConL(l,M);
            long max = -1000000000;
            for(int i=r;i>=M;i--){
                max = Math.Max(max,Con.Query(-i)+UseConL(i));
                use[i] = Math.Max(max,use[i]);
            }
        }
        {
            ConvexHullTrick Con = ConR(M,r);
            long max = -1000000000;
            for(int i=l;i<=M;i++){
                max = Math.Max(max,Con.Query(-(N-1-i))+UseConR(i));
                use[i] = Math.Max(max,use[i]);
            }
        }
    }
}
struct ConvexHullTrick{
    long[] A;
    long[] B;
    //C[i]はi番目の点に適用するのがi+1番目の点に適用するよりも大きくなる最大のx 単調増加になる
    long[] C;
    int p;
    int find;
    public ConvexHullTrick(int N){
        A = new long[N];
        B = new long[N];
        C = new long[N];
        p = 0;
        find = 0;
    }
    //aは単調増加でないといけない
    public void Add(long a,long b){
        if(p == 0){
            A[0] = a;
            B[0] = b;;
            p++;
        }
        else{
            for(int i=p;i>0;i--){
                long X = Compare(A[i-1],B[i-1],a,b);
                if(i == 1 || X > C[i-2]){
                    C[i-1] = X;
                    A[i] = a;
                    B[i] = b;
                    p = i+1;
                    break;
                }
            }
        }
    }
    //1つはAddしていないといけない
    public long Query(long x){
        return Calc(x,findMax(x));
    }
    int findMax(long x){
        find = Math.Min(find,p-1);
        while(find < p-1 && C[find] < x){
            find++;
        }
        while(find > 0 && C[find-1] >= x){
            find--;
        }
        return find;
    }
    long Calc(long x,int i){
        return A[i]*x + B[i];
    }
    //(a1,b1)に適用する方が(a2,b2)に適用するより大きくなる最大のx
    long Compare(long a1,long b1,long a2,long b2){
        return (b1-b2-1)/(a2-a1) - ((b1-b2-1)%(a2-a1) < 0 ? 1 : 0);
    }
}

Submission Info

Submission Time
Task F - Contest with Drinks Hard
User leign
Language C# (Mono 4.6.2.0)
Score 0
Code Size 5373 Byte
Status RE
Exec Time 1125 ms
Memory 72192 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 19
WA × 31
RE × 4
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt
Case Name Status Exec Time Memory
sample_01.txt AC 22 ms 11220 KB
sample_02.txt AC 21 ms 9172 KB
subtask_1_high_equaly_01.txt WA 456 ms 50656 KB
subtask_1_high_equaly_02.txt WA 335 ms 51620 KB
subtask_1_high_equaly_03.txt AC 99 ms 15692 KB
subtask_1_high_equaly_04.txt WA 705 ms 49056 KB
subtask_1_high_rand_01.txt WA 458 ms 50088 KB
subtask_1_high_rand_02.txt WA 332 ms 46528 KB
subtask_1_high_rand_03.txt WA 486 ms 46960 KB
subtask_1_high_rand_04.txt WA 636 ms 47832 KB
subtask_1_killer_01.txt RE 20 ms 10720 KB
subtask_1_killer_02.txt RE 20 ms 10720 KB
subtask_1_low_equaly_01.txt WA 762 ms 46308 KB
subtask_1_low_equaly_02.txt WA 519 ms 53632 KB
subtask_1_low_equaly_03.txt WA 601 ms 57732 KB
subtask_1_low_equaly_04.txt WA 275 ms 48716 KB
subtask_1_low_rand_01.txt WA 594 ms 47136 KB
subtask_1_low_rand_02.txt WA 452 ms 41676 KB
subtask_1_low_rand_03.txt WA 404 ms 43160 KB
subtask_1_low_rand_04.txt WA 759 ms 50504 KB
subtask_1_max_high_equaly_01.txt WA 1099 ms 64464 KB
subtask_1_max_high_equaly_02.txt WA 1113 ms 66092 KB
subtask_1_max_high_equaly_03.txt WA 1111 ms 65000 KB
subtask_1_max_high_equaly_04.txt WA 1099 ms 64464 KB
subtask_1_max_high_rand_01.txt WA 1104 ms 62992 KB
subtask_1_max_high_rand_02.txt WA 1115 ms 66584 KB
subtask_1_max_high_rand_03.txt WA 1095 ms 66416 KB
subtask_1_max_high_rand_04.txt WA 1093 ms 64108 KB
subtask_1_max_low_equaly_01.txt WA 1100 ms 62824 KB
subtask_1_max_low_equaly_02.txt WA 1084 ms 62040 KB
subtask_1_max_low_equaly_03.txt WA 1098 ms 59356 KB
subtask_1_max_low_equaly_04.txt WA 1074 ms 64652 KB
subtask_1_max_low_rand_01.txt WA 1064 ms 60656 KB
subtask_1_max_low_rand_02.txt WA 1125 ms 60448 KB
subtask_1_max_low_rand_03.txt WA 1100 ms 61952 KB
subtask_1_max_low_rand_04.txt WA 1062 ms 64956 KB
subtask_1_max_rand_equaly_01.txt AC 1075 ms 66680 KB
subtask_1_max_rand_equaly_02.txt AC 1075 ms 64580 KB
subtask_1_max_rand_equaly_03.txt AC 1041 ms 66680 KB
subtask_1_max_rand_equaly_04.txt AC 1072 ms 64560 KB
subtask_1_max_rand_rand_01.txt AC 1055 ms 64636 KB
subtask_1_max_rand_rand_02.txt AC 1050 ms 64632 KB
subtask_1_max_rand_rand_03.txt AC 1067 ms 66612 KB
subtask_1_max_rand_rand_04.txt AC 1046 ms 72192 KB
subtask_1_min_rand_rand_01.txt RE 20 ms 10720 KB
subtask_1_min_rand_rand_02.txt RE 20 ms 10720 KB
subtask_1_rand_equaly_01.txt AC 61 ms 16216 KB
subtask_1_rand_equaly_02.txt AC 620 ms 51052 KB
subtask_1_rand_equaly_03.txt AC 288 ms 37472 KB
subtask_1_rand_equaly_04.txt AC 495 ms 46612 KB
subtask_1_rand_rand_01.txt AC 729 ms 63940 KB
subtask_1_rand_rand_02.txt AC 439 ms 39672 KB
subtask_1_rand_rand_03.txt AC 659 ms 57328 KB
subtask_1_rand_rand_04.txt AC 309 ms 33552 KB