Submission #1174425
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+1); 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+1); 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)+(i == N-1 ? 0 : DPR[i+1])); 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)+(i == 0 ? 0 : DPL[i-1])); 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 | 5427 Byte |
Status | WA |
Exec Time | 1131 ms |
Memory | 68628 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1400 | ||||||
Status |
|
|
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 | 465 ms | 50692 KB |
subtask_1_high_equaly_02.txt | WA | 339 ms | 47596 KB |
subtask_1_high_equaly_03.txt | AC | 98 ms | 17556 KB |
subtask_1_high_equaly_04.txt | WA | 718 ms | 53304 KB |
subtask_1_high_rand_01.txt | WA | 463 ms | 50092 KB |
subtask_1_high_rand_02.txt | WA | 336 ms | 46576 KB |
subtask_1_high_rand_03.txt | WA | 492 ms | 53192 KB |
subtask_1_high_rand_04.txt | WA | 635 ms | 49864 KB |
subtask_1_killer_01.txt | AC | 22 ms | 13268 KB |
subtask_1_killer_02.txt | AC | 22 ms | 11220 KB |
subtask_1_low_equaly_01.txt | WA | 772 ms | 50404 KB |
subtask_1_low_equaly_02.txt | WA | 537 ms | 58232 KB |
subtask_1_low_equaly_03.txt | WA | 609 ms | 53652 KB |
subtask_1_low_equaly_04.txt | WA | 275 ms | 48716 KB |
subtask_1_low_rand_01.txt | WA | 594 ms | 51232 KB |
subtask_1_low_rand_02.txt | WA | 469 ms | 43724 KB |
subtask_1_low_rand_03.txt | WA | 403 ms | 49308 KB |
subtask_1_low_rand_04.txt | WA | 762 ms | 52576 KB |
subtask_1_max_high_equaly_01.txt | WA | 1114 ms | 66480 KB |
subtask_1_max_high_equaly_02.txt | WA | 1122 ms | 61936 KB |
subtask_1_max_high_equaly_03.txt | WA | 1123 ms | 62880 KB |
subtask_1_max_high_equaly_04.txt | WA | 1117 ms | 64532 KB |
subtask_1_max_high_rand_01.txt | WA | 1107 ms | 62972 KB |
subtask_1_max_high_rand_02.txt | WA | 1113 ms | 64468 KB |
subtask_1_max_high_rand_03.txt | WA | 1109 ms | 64208 KB |
subtask_1_max_high_rand_04.txt | WA | 1105 ms | 62028 KB |
subtask_1_max_low_equaly_01.txt | WA | 1084 ms | 58480 KB |
subtask_1_max_low_equaly_02.txt | WA | 1124 ms | 62744 KB |
subtask_1_max_low_equaly_03.txt | WA | 1100 ms | 60516 KB |
subtask_1_max_low_equaly_04.txt | WA | 1084 ms | 62348 KB |
subtask_1_max_low_rand_01.txt | WA | 1084 ms | 60660 KB |
subtask_1_max_low_rand_02.txt | WA | 1131 ms | 60576 KB |
subtask_1_max_low_rand_03.txt | WA | 1080 ms | 66228 KB |
subtask_1_max_low_rand_04.txt | WA | 1082 ms | 64956 KB |
subtask_1_max_rand_equaly_01.txt | AC | 1065 ms | 64548 KB |
subtask_1_max_rand_equaly_02.txt | AC | 1059 ms | 64532 KB |
subtask_1_max_rand_equaly_03.txt | AC | 1060 ms | 62552 KB |
subtask_1_max_rand_equaly_04.txt | AC | 1058 ms | 64544 KB |
subtask_1_max_rand_rand_01.txt | AC | 1064 ms | 68628 KB |
subtask_1_max_rand_rand_02.txt | AC | 1061 ms | 62484 KB |
subtask_1_max_rand_rand_03.txt | AC | 1069 ms | 66520 KB |
subtask_1_max_rand_rand_04.txt | AC | 1090 ms | 68628 KB |
subtask_1_min_rand_rand_01.txt | AC | 23 ms | 11220 KB |
subtask_1_min_rand_rand_02.txt | AC | 22 ms | 11220 KB |
subtask_1_rand_equaly_01.txt | AC | 62 ms | 20312 KB |
subtask_1_rand_equaly_02.txt | AC | 665 ms | 55272 KB |
subtask_1_rand_equaly_03.txt | AC | 293 ms | 33504 KB |
subtask_1_rand_equaly_04.txt | AC | 500 ms | 48660 KB |
subtask_1_rand_rand_01.txt | AC | 740 ms | 62376 KB |
subtask_1_rand_rand_02.txt | AC | 445 ms | 41720 KB |
subtask_1_rand_rand_03.txt | AC | 660 ms | 59296 KB |
subtask_1_rand_rand_04.txt | AC | 313 ms | 27408 KB |