Submission #3010350
Source Code Expand
#include<bits/stdc++.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; const long long d2=500000004; const double EPS=1e-6; const double PI=acos(-1.0); int ABS(int a){return max(a,-a);} long long ABS(long long a){return max(a,-a);} int p[310000]; int sum[310000]; vector<pair<int,int> >g[310000]; int dp[310000]; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return -1; if(c<=a&&b<=d)return segtree[e]; int L=query(a,(a+b)/2,c,d,e*2); int R=query((a+b)/2+1,b,c,d,e*2+1); if(L==-1)return R; if(R==-1)return L; if(dp[L]+(R-L)-(sum[R]-sum[L])<dp[R])return L; else return R; } void update(int a){ a+=262144; a/=2; while(a){ int L=segtree[a*2]; int R=segtree[a*2+1]; if(dp[L]+(R-L)-(sum[R]-sum[L])<dp[R])segtree[a]=L; else segtree[a]=R; a/=2; } } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<290000;i++)sum[i+1]=sum[i]+p[i]; int b;scanf("%d",&b); for(int i=0;i<262144;i++)segtree[i+262144]=i; for(int i=0;i<=290000;i++)dp[i]=mod; dp[0]=0; for(int i=0;i<262144;i++)update(i); for(int i=0;i<b;i++){ int l,r;scanf("%d%d",&l,&r);l--; g[l].push_back(make_pair(r,(r-l)-(sum[r]-sum[l]))); } for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ int at=query(0,262143,i,g[i][j].first,1); dp[g[i][j].first]=dp[at]+(g[i][j].first-at)-(sum[g[i][j].first]-sum[at]); update(g[i][j].first); } dp[i+1]=min(dp[i+1],dp[i]+p[i]); update(i+1); dp[i]=mod; update(i); } printf("%d\n",dp[a]); }
Submission Info
Submission Time | |
---|---|
Task | F - NRE |
User | fxt |
Language | C++ (GCC 5.4.1) |
Score | 1000 |
Code Size | 1593 Byte |
Status | AC |
Exec Time | 248 ms |
Memory | 18816 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int a;scanf("%d",&a); ^ ./Main.cpp:38:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for(int i=0;i<a;i++)scanf("%d",p+i); ^ ./Main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int b;scanf("%d",&b); ^ ./Main.cpp:47:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int l,r;scanf("%d%d",&l,&r);l--; ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example_0, example_1, example_2, example_3, example_4, example_5, example_6 |
All | cent_0, cent_1, cent_2, cent_3, cent_4, cent_5, cent_6, cent_7, cent_8, cent_9, example_0, example_1, example_2, example_3, example_4, example_5, example_6, full_0, full_1, full_10, full_11, full_12, full_13, full_14, full_15, full_16, full_17, full_18, full_19, full_2, full_3, full_4, full_5, full_6, full_7, full_8, full_9, maxrand_0, maxrand_1, maxrand_10, maxrand_11, maxrand_12, maxrand_13, maxrand_14, maxrand_15, maxrand_16, maxrand_17, maxrand_18, maxrand_19, maxrand_2, maxrand_20, maxrand_21, maxrand_22, maxrand_23, maxrand_24, maxrand_25, maxrand_26, maxrand_27, maxrand_28, maxrand_29, maxrand_3, maxrand_4, maxrand_5, maxrand_6, maxrand_7, maxrand_8, maxrand_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4, small_5, small_6, small_7, small_8, small_9, smallwidth_0, smallwidth_1, smallwidth_10, smallwidth_11, smallwidth_12, smallwidth_13, smallwidth_14, smallwidth_15, smallwidth_16, smallwidth_17, smallwidth_18, smallwidth_19, smallwidth_2, smallwidth_20, smallwidth_21, smallwidth_22, smallwidth_23, smallwidth_24, smallwidth_25, smallwidth_26, smallwidth_27, smallwidth_28, smallwidth_29, smallwidth_3, smallwidth_4, smallwidth_5, smallwidth_6, smallwidth_7, smallwidth_8, smallwidth_9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
cent_0 | AC | 219 ms | 16120 KB |
cent_1 | AC | 227 ms | 16640 KB |
cent_2 | AC | 213 ms | 16116 KB |
cent_3 | AC | 220 ms | 16120 KB |
cent_4 | AC | 222 ms | 16632 KB |
cent_5 | AC | 213 ms | 16372 KB |
cent_6 | AC | 221 ms | 16120 KB |
cent_7 | AC | 216 ms | 15860 KB |
cent_8 | AC | 228 ms | 16640 KB |
cent_9 | AC | 213 ms | 16500 KB |
example_0 | AC | 20 ms | 12544 KB |
example_1 | AC | 20 ms | 12544 KB |
example_2 | AC | 20 ms | 12544 KB |
example_3 | AC | 20 ms | 12544 KB |
example_4 | AC | 20 ms | 12544 KB |
example_5 | AC | 20 ms | 12544 KB |
example_6 | AC | 20 ms | 12544 KB |
full_0 | AC | 76 ms | 12800 KB |
full_1 | AC | 231 ms | 16896 KB |
full_10 | AC | 76 ms | 12800 KB |
full_11 | AC | 230 ms | 16896 KB |
full_12 | AC | 77 ms | 12800 KB |
full_13 | AC | 229 ms | 16896 KB |
full_14 | AC | 76 ms | 12800 KB |
full_15 | AC | 229 ms | 16896 KB |
full_16 | AC | 76 ms | 12800 KB |
full_17 | AC | 230 ms | 16896 KB |
full_18 | AC | 77 ms | 12800 KB |
full_19 | AC | 248 ms | 16896 KB |
full_2 | AC | 77 ms | 12800 KB |
full_3 | AC | 232 ms | 16896 KB |
full_4 | AC | 76 ms | 12800 KB |
full_5 | AC | 230 ms | 16896 KB |
full_6 | AC | 76 ms | 12800 KB |
full_7 | AC | 234 ms | 16896 KB |
full_8 | AC | 76 ms | 12800 KB |
full_9 | AC | 228 ms | 16896 KB |
maxrand_0 | AC | 78 ms | 12800 KB |
maxrand_1 | AC | 229 ms | 16768 KB |
maxrand_10 | AC | 77 ms | 12800 KB |
maxrand_11 | AC | 229 ms | 16768 KB |
maxrand_12 | AC | 80 ms | 12800 KB |
maxrand_13 | AC | 238 ms | 16768 KB |
maxrand_14 | AC | 77 ms | 12800 KB |
maxrand_15 | AC | 245 ms | 16768 KB |
maxrand_16 | AC | 78 ms | 12800 KB |
maxrand_17 | AC | 237 ms | 16768 KB |
maxrand_18 | AC | 78 ms | 12800 KB |
maxrand_19 | AC | 230 ms | 16768 KB |
maxrand_2 | AC | 76 ms | 12800 KB |
maxrand_20 | AC | 77 ms | 12800 KB |
maxrand_21 | AC | 232 ms | 16768 KB |
maxrand_22 | AC | 78 ms | 12800 KB |
maxrand_23 | AC | 230 ms | 16768 KB |
maxrand_24 | AC | 78 ms | 12800 KB |
maxrand_25 | AC | 232 ms | 16768 KB |
maxrand_26 | AC | 78 ms | 12800 KB |
maxrand_27 | AC | 233 ms | 16768 KB |
maxrand_28 | AC | 76 ms | 12800 KB |
maxrand_29 | AC | 232 ms | 16768 KB |
maxrand_3 | AC | 229 ms | 16768 KB |
maxrand_4 | AC | 77 ms | 12800 KB |
maxrand_5 | AC | 234 ms | 16768 KB |
maxrand_6 | AC | 77 ms | 12800 KB |
maxrand_7 | AC | 232 ms | 16768 KB |
maxrand_8 | AC | 77 ms | 12800 KB |
maxrand_9 | AC | 237 ms | 16768 KB |
rand_0 | AC | 232 ms | 18816 KB |
rand_1 | AC | 128 ms | 14720 KB |
rand_10 | AC | 234 ms | 16768 KB |
rand_11 | AC | 100 ms | 13952 KB |
rand_12 | AC | 231 ms | 16768 KB |
rand_13 | AC | 171 ms | 15360 KB |
rand_14 | AC | 233 ms | 16768 KB |
rand_15 | AC | 104 ms | 14208 KB |
rand_16 | AC | 236 ms | 16768 KB |
rand_17 | AC | 133 ms | 14720 KB |
rand_18 | AC | 234 ms | 16768 KB |
rand_19 | AC | 210 ms | 16128 KB |
rand_2 | AC | 235 ms | 16768 KB |
rand_3 | AC | 167 ms | 15488 KB |
rand_4 | AC | 241 ms | 16768 KB |
rand_5 | AC | 106 ms | 14592 KB |
rand_6 | AC | 232 ms | 16768 KB |
rand_7 | AC | 142 ms | 14976 KB |
rand_8 | AC | 237 ms | 16768 KB |
rand_9 | AC | 80 ms | 13184 KB |
small_0 | AC | 20 ms | 12544 KB |
small_1 | AC | 20 ms | 12544 KB |
small_2 | AC | 20 ms | 12544 KB |
small_3 | AC | 20 ms | 12544 KB |
small_4 | AC | 20 ms | 12544 KB |
small_5 | AC | 20 ms | 12544 KB |
small_6 | AC | 20 ms | 12544 KB |
small_7 | AC | 20 ms | 12544 KB |
small_8 | AC | 20 ms | 12544 KB |
small_9 | AC | 20 ms | 12544 KB |
smallwidth_0 | AC | 76 ms | 12800 KB |
smallwidth_1 | AC | 219 ms | 17024 KB |
smallwidth_10 | AC | 76 ms | 12800 KB |
smallwidth_11 | AC | 191 ms | 17024 KB |
smallwidth_12 | AC | 77 ms | 12800 KB |
smallwidth_13 | AC | 226 ms | 16896 KB |
smallwidth_14 | AC | 76 ms | 12800 KB |
smallwidth_15 | AC | 190 ms | 17024 KB |
smallwidth_16 | AC | 76 ms | 12800 KB |
smallwidth_17 | AC | 222 ms | 17024 KB |
smallwidth_18 | AC | 76 ms | 12800 KB |
smallwidth_19 | AC | 195 ms | 17024 KB |
smallwidth_2 | AC | 76 ms | 12800 KB |
smallwidth_20 | AC | 76 ms | 12800 KB |
smallwidth_21 | AC | 223 ms | 17024 KB |
smallwidth_22 | AC | 76 ms | 12800 KB |
smallwidth_23 | AC | 190 ms | 17024 KB |
smallwidth_24 | AC | 77 ms | 12800 KB |
smallwidth_25 | AC | 221 ms | 17024 KB |
smallwidth_26 | AC | 76 ms | 12800 KB |
smallwidth_27 | AC | 193 ms | 17024 KB |
smallwidth_28 | AC | 76 ms | 12800 KB |
smallwidth_29 | AC | 221 ms | 17024 KB |
smallwidth_3 | AC | 190 ms | 17024 KB |
smallwidth_4 | AC | 76 ms | 12800 KB |
smallwidth_5 | AC | 225 ms | 16896 KB |
smallwidth_6 | AC | 76 ms | 12800 KB |
smallwidth_7 | AC | 198 ms | 17024 KB |
smallwidth_8 | AC | 76 ms | 12800 KB |
smallwidth_9 | AC | 219 ms | 16896 KB |