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
WA × 3
WA × 14
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