Submission #1407399
Source Code Expand
#include <stdio.h> #include <algorithm> using namespace std; int N,L[100100],A[100100],B[100100]; long long P[100100]; pair<long long, int> V[100100]; void in(int x) { while (x <= N){ B[x]++; x += x & (-x); } } int out(int x) { int r = 0; while (x){ r += B[x]; x -= x & (-x); } return r; } int main() { scanf ("%d",&N); for (int i=0;i<N;i++) scanf ("%lld",&P[i]); for (int i=0;i<N;i++) scanf ("%d",&L[i]); for (int i=1;i<N;i++) P[i] += P[i-1]; for (int i=0;i<N;i++) V[i] = {P[i],i}; sort(V,V+N); for (int i=0;i<N;i++) if (V[i].first - (i ? V[i-1].first : 0) < L[i]){ puts("-1"); return 0; } for (int i=0;i<N;i++) A[V[i].second] = i + 1; long long ans = 0; for (int i=0;i<N;i++){ ans += i - out(A[i]); in(A[i]); } printf ("%lld\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - Air Pollution |
User | august14 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 838 Byte |
Status | AC |
Exec Time | 29 ms |
Memory | 3712 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:28:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf ("%d",&N); ^ ./Main.cpp:29:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i=0;i<N;i++) scanf ("%lld",&P[i]); ^ ./Main.cpp:30:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i=0;i<N;i++) scanf ("%d",&L[i]); ^
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, large-random-0.txt, large-random-1.txt, large-random-2.txt, large-random-3.txt, large-random-4.txt, medium-random-0.txt, medium-random-1.txt, medium-random-2.txt, medium-random-3.txt, medium-random-4.txt, medium-random-5.txt, medium-random-6.txt, medium-random-7.txt, medium-random-8.txt, medium-random-9.txt, overflow1.txt, overflow2.txt, small-random-0.txt, small-random-1.txt, small-random-10.txt, small-random-11.txt, small-random-12.txt, small-random-13.txt, small-random-14.txt, small-random-2.txt, small-random-3.txt, small-random-4.txt, small-random-5.txt, small-random-6.txt, small-random-7.txt, small-random-8.txt, small-random-9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample1.txt | AC | 1 ms | 128 KB |
00_sample2.txt | AC | 0 ms | 128 KB |
00_sample3.txt | AC | 1 ms | 128 KB |
large-random-0.txt | AC | 25 ms | 2816 KB |
large-random-1.txt | AC | 25 ms | 3712 KB |
large-random-2.txt | AC | 25 ms | 3584 KB |
large-random-3.txt | AC | 20 ms | 2688 KB |
large-random-4.txt | AC | 25 ms | 3584 KB |
medium-random-0.txt | AC | 1 ms | 256 KB |
medium-random-1.txt | AC | 1 ms | 256 KB |
medium-random-2.txt | AC | 1 ms | 256 KB |
medium-random-3.txt | AC | 1 ms | 256 KB |
medium-random-4.txt | AC | 1 ms | 256 KB |
medium-random-5.txt | AC | 1 ms | 256 KB |
medium-random-6.txt | AC | 1 ms | 256 KB |
medium-random-7.txt | AC | 1 ms | 256 KB |
medium-random-8.txt | AC | 1 ms | 256 KB |
medium-random-9.txt | AC | 1 ms | 256 KB |
overflow1.txt | AC | 29 ms | 3712 KB |
overflow2.txt | AC | 28 ms | 3712 KB |
small-random-0.txt | AC | 1 ms | 256 KB |
small-random-1.txt | AC | 1 ms | 256 KB |
small-random-10.txt | AC | 1 ms | 128 KB |
small-random-11.txt | AC | 1 ms | 128 KB |
small-random-12.txt | AC | 1 ms | 128 KB |
small-random-13.txt | AC | 1 ms | 128 KB |
small-random-14.txt | AC | 1 ms | 128 KB |
small-random-2.txt | AC | 1 ms | 256 KB |
small-random-3.txt | AC | 1 ms | 256 KB |
small-random-4.txt | AC | 1 ms | 256 KB |
small-random-5.txt | AC | 1 ms | 256 KB |
small-random-6.txt | AC | 1 ms | 256 KB |
small-random-7.txt | AC | 1 ms | 256 KB |
small-random-8.txt | AC | 1 ms | 256 KB |
small-random-9.txt | AC | 1 ms | 256 KB |