Submission #3001951
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
vector <int> v[200005];
int n,i,c0,cost[200005],q,j,x,t,y,d[800005],dp[200005],b[200005];
int query(int k,int t,int w,int x,int y)
{
if ((t>y) || (x>w))
return 2000000000;
if ((x<=t) && (w<=y))
return d[k];
int mid=(t+w)/2;
return min(query(k*2,t,mid,x,y),query(k*2+1,mid+1,w,x,y));
}
void xiugai(int k,int t,int w,int x,int y)
{
if ((t>x) || (w<x))
return;
if (t==w)
{
d[k]=y;
return;
}
int mid=(t+w)/2;
xiugai(k*2,t,mid,x,y);
xiugai(k*2+1,mid+1,w,x,y);
d[k]=min(d[k*2],d[k*2+1]);
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&b[i]);
if (b[i]==0)
c0++;
if (b[i]==0)
cost[i]=-1;
else
cost[i]=1;
}
scanf("%d",&q);
for (i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
memset(d,127,sizeof(d));
memset(dp,127,sizeof(dp));
dp[0]=0;
for (i=1;i<=n;i++)
{
for (j=0;j<v[i].size();j++)
{
x=v[i][j];
t=min(dp[i-1],query(1,1,n,max(i-1,1),x));
if (t<dp[x])
{
dp[x]=t;
xiugai(1,1,n,x,t);
}
}
dp[i]=min(dp[i],dp[i-1]+cost[i]);
}
printf("%d",dp[n]+c0);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - HSI |
User |
shenzekai |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1250 Byte |
Status |
WA |
Exec Time |
4 ms |
Memory |
9600 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:33:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b[i]);
^
./Main.cpp:41:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_0, example_1, example_2 |
All |
example_0, example_1, example_2, handmade_0, rand_0, rand_1, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9 |
Case Name |
Status |
Exec Time |
Memory |
example_0 |
WA |
4 ms |
9600 KB |
example_1 |
WA |
4 ms |
9600 KB |
example_2 |
WA |
4 ms |
9600 KB |
handmade_0 |
WA |
4 ms |
9600 KB |
rand_0 |
WA |
4 ms |
9600 KB |
rand_1 |
WA |
4 ms |
9600 KB |
rand_2 |
WA |
4 ms |
9600 KB |
rand_3 |
WA |
4 ms |
9600 KB |
rand_4 |
WA |
4 ms |
9600 KB |
rand_5 |
WA |
4 ms |
9600 KB |
rand_6 |
WA |
4 ms |
9600 KB |
rand_7 |
WA |
4 ms |
9600 KB |
rand_8 |
WA |
4 ms |
9600 KB |
rand_9 |
WA |
4 ms |
9600 KB |