Submission #171665


Source Code Expand

Copy
#include <cstdio>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <queue>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <complex>
#include <numeric>
#include <map>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<double> vec;
typedef vector<vec> mat;
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
#define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end())
#define SORTN(x,n) sort((x),(x)+(n))
#define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define COUNT(x,c) count((x).begin(),(x).end(),(c))
#define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
#define REVERSE(x) reverse((x).begin(),(x).end())
#define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
#define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
#define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
#define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
#define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
#define BS(x,a) binary_search((x).begin(),(x).end(),(a))
#define BS2(x,n,a) binary_search((x),(x)+(n),(a))
#define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
#define NP(x) next_permutation((x).begin(),(x).end())
#define MM(x,p) memset((x),(p),sizeof(x))
#define SQ(x) (x)*(x)
#define SC(c1,c2) strcmp(c1,c2)==0
#define mp make_pair
#define INF (1<<29)
#define INFL (1LL<<50)
#define fi first
#define se second
#define MOD 1000000007
#define EPS 1e-8

ll extgcd(ll a,ll b,ll &x,ll &y)
{
	ll r = a;
	if(b)r=extgcd(b,a%b,y,x),y-=(a/b)*x;
	else x=1,y=0;
	return r;
}
ll mod_inverse(ll a)
{
	ll x,y;
	ll m=MOD;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

int N;
int A[100000];

int main()
{
	scanf("%d",&N);
	int ls=-1;
	ll ans=1;
	int sz=0;
	rep(i,N)
	{
		scanf("%d",&A[i]);
		if(A[i]==-1)sz++;
		if(A[i]!=-1&&sz)
		{
			ll ap=1;
			rep(j,sz)ap=ap*(A[i]-ls+j+1)%MOD;
			rep(j,sz)ap=ap*mod_inverse(j+1)%MOD;
			ans=(ans*ap)%MOD;
		}
		if(A[i]!=-1)ls=A[i],sz=0;
	}
	printf("%lld\n",ans);
}

Submission Info

Submission Time
Task C - タコヤ木
User namonakiacc
Language C++ (G++ 4.6.4)
Score 100
Code Size 2735 Byte
Status AC
Exec Time 23 ms
Memory 928 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:91:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 19 ms 800 KB
sample_02.txt AC 21 ms 816 KB
sample_03.txt AC 21 ms 924 KB
subtask1_01.txt AC 20 ms 808 KB
subtask1_02.txt AC 21 ms 924 KB
subtask1_03.txt AC 21 ms 928 KB
subtask1_04.txt AC 20 ms 744 KB
subtask1_05.txt AC 20 ms 800 KB
subtask1_06.txt AC 20 ms 800 KB
subtask1_07.txt AC 20 ms 804 KB
subtask1_08.txt AC 20 ms 924 KB
subtask1_09.txt AC 20 ms 928 KB
subtask1_10.txt AC 20 ms 800 KB
subtask1_11.txt AC 21 ms 800 KB
subtask1_12.txt AC 20 ms 800 KB
subtask2_01.txt AC 21 ms 804 KB
subtask2_02.txt AC 22 ms 928 KB
subtask2_03.txt AC 20 ms 804 KB
subtask2_04.txt AC 19 ms 928 KB
subtask2_05.txt AC 19 ms 800 KB
subtask2_06.txt AC 21 ms 812 KB
subtask2_07.txt AC 21 ms 796 KB
subtask2_08.txt AC 20 ms 800 KB
subtask2_09.txt AC 21 ms 924 KB
subtask2_10.txt AC 21 ms 928 KB
subtask2_11.txt AC 21 ms 800 KB
subtask2_12.txt AC 21 ms 924 KB
subtask3_01.txt AC 22 ms 800 KB
subtask3_02.txt AC 21 ms 808 KB
subtask3_03.txt AC 21 ms 924 KB
subtask3_04.txt AC 20 ms 800 KB
subtask3_05.txt AC 23 ms 796 KB
subtask3_06.txt AC 21 ms 804 KB
subtask3_07.txt AC 22 ms 928 KB
subtask3_08.txt AC 21 ms 924 KB
subtask3_09.txt AC 22 ms 924 KB
subtask3_10.txt AC 23 ms 808 KB
subtask3_11.txt AC 22 ms 804 KB
subtask3_12.txt AC 22 ms 928 KB