Submission #907700
Source Code Expand
/* AtCoder My Practice * author: Leonardone @ NEETSDKASU */ #include <stdio.h> #define N_MAX (200001) typedef struct _range { int upper, lower; struct _range *ubound, *lbound; } Range; Range *newRange(int lower, int upper) { Range *range = (Range*)malloc(sizeof(Range)); range->lower = lower; range->upper = upper; return range; } int idx[N_MAX]; long long sum; Range range; void calc(int value, int index) { Range *tmp = ⦥ long long len; for (;;) { if (tmp->lower <= index && index <= tmp->upper) { len = (long long)(tmp->upper - tmp->lower + 1); sum += (len * (len + 1LL) / 2LL) * (long long)value; len = (long long)(tmp->upper - index); sum -= (len * (len + 1LL) / 2LL) * (long long)value; len = (long long)(index - tmp->lower); sum -= (len * (len + 1LL) / 2LL) * (long long)value; if (tmp->lower == index) { tmp->lower++; } else if (tmp->upper == index) { tmp->upper--; } else { tmp->lbound = newRange(tmp->lower, index - 1); tmp->ubound = newRange(index + 1, tmp->upper); tmp->lower = tmp->upper = index; } break; } else if (index < tmp->lower) { tmp = tmp->lbound; } else { tmp = tmp->ubound; } } } int main(void){ int i, n; scanf("%d", &n); for (i = 0; i < n; i++) { int a; scanf("%d", &a); idx[a] = i; } range.upper = n - 1; for (i = 1; i <= n; i++) { calc(i, idx[i]); } printf("%lld\n", sum); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | neetsdkasu |
Language | C (GCC 5.4.1) |
Score | 400 |
Code Size | 1801 Byte |
Status | AC |
Exec Time | 78 ms |
Memory | 5120 KB |
Compile Error
./Main.c: In function ‘newRange’: ./Main.c:14:28: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration] Range *range = (Range*)malloc(sizeof(Range)); ^ ./Main.c:14:28: warning: incompatible implicit declaration of built-in function ‘malloc’ ./Main.c:14:28: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’ ./Main.c: In function ‘main’: ./Main.c:57:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.c:61:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &a); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
corner0 | AC | 24 ms | 896 KB |
corner1 | AC | 24 ms | 896 KB |
corner2 | AC | 1 ms | 128 KB |
corner3 | AC | 25 ms | 896 KB |
example0 | AC | 1 ms | 128 KB |
example1 | AC | 1 ms | 128 KB |
example2 | AC | 1 ms | 128 KB |
maxrand0 | AC | 77 ms | 5120 KB |
maxrand1 | AC | 78 ms | 5120 KB |
maxrand2 | AC | 77 ms | 5120 KB |
rand0 | AC | 1 ms | 128 KB |
rand1 | AC | 1 ms | 128 KB |
rand2 | AC | 1 ms | 128 KB |