QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#841440#8708. Portalzhassyn#0 9ms5840kbC++202.1kb2025-01-03 19:03:312025-01-03 19:03:32

Judging History

This is the latest submission verdict.

  • [2025-01-03 19:03:32]
  • Judged
  • Verdict: 0
  • Time: 9ms
  • Memory: 5840kb
  • [2025-01-03 19:03:31]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 316 + 10, len = 315, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll n, x[N], d[N], dp[N];
void subtask2(){
	ll ans = 0;
	dp[1] = 1;
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= x[i]; j++){
			if(i + d[i] * j > n || d[i] == 0) break;
			dp[i + d[i] * j] += dp[i];
			dp[i + d[i] * j] %= mod;
		}
		//cout << dp[i] << endl;
		ans += dp[i];
		ans %= mod;
	}
	cout << ans;
}
void subtask3(){
	ll sum = 1, ans = 1;
	set <pll> st;
	dp[1] = 1;
	st.insert({x[1] + 1, 1});
	for(ll i = 2; i <= n; i++){
		while((ll)st.size() != 0){
			ll v = st.begin()->F;
			if(v < i){
				//cout << st.begin()->F << " "<< st.begin()->S << " INFO\n";
				sum = subr(sum, dp[st.begin()->S]);
				st.erase(st.begin());
			} else break;
		}
		ans += sum;
		ans %= mod;
		dp[i] = sum;
		st.insert({x[i] + i, i});
		//cout << i << " "<< sum << endl;
		sum = um(sum, 2LL);
	}
	cout << ans;
}
ll mas[M][M];
void subtask4(){
	ll ans = 0;
	dp[1] = 1;
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= 316; j++){
			dp[i] += mas[j][i % j];
			dp[i] %= mod;
		}
		ans += dp[i];
		ans %= mod;
		if(d[i] == 0) continue;
		if(d[i] <= 316){
			mas[d[i]][i % d[i]] += dp[i];
			mas[d[i]][i % d[i]] %= mod;
		} else{
			for(ll j = 1; j <= x[i]; j++){
				if(j * d[i] + i > n) break;
				dp[j * d[i] + i] += dp[i];
				dp[j * d[i] + i] %= mod;
			}
		}
	}
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n;
	bool c3 = true, c4 = true;
	for(ll i = 1; i <= n; i++){
		cin >> d[i] >> x[i];
		if(d[i] != 1) c3 = false;
		if(x[i] != 1e9) c4 = false;
	}
	if(n <= 10000){
		subtask2();
		return 0;
	}
	if(c3){
		subtask3();
		return 0;
	}
	if(c4){
		subtask4();
		return 0;
	}
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5660kb

input:

1
1 -1

output:

1

result:

wrong answer 1st lines differ - expected: '-1', found: '1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #40:

score: 0
Wrong Answer
time: 9ms
memory: 5840kb

input:

99840
-359536 735499
-710626 400619
-468266 -282389
-192706 43659
204034 -543669
-100576 -749013
-118006 -283125
-341276 405771
560934 835595
-923936 506603
239724 956299
-680746 -737237
286204 982795
-847576 -282389
-949666 986475
996684 -429589
672984 -133717
140954 696491
-879116 -442837
985064 7...

output:


result:

wrong answer 1st lines differ - expected: '610880', found: ''

Subtask #4:

score: 0
Wrong Answer

Test #59:

score: 29
Accepted
time: 0ms
memory: 3592kb

input:

5
0 0
1 0
-1 0
0 1
0 -1

output:

1

result:

ok single line: '1'

Test #60:

score: 0
Wrong Answer
time: 1ms
memory: 3880kb

input:

100
-30 -13
-22 -19
32 9
-18 -11
50 19
16 5
-50 -17
-46 -21
10 -1
-56 -19
2 -11
-24 -15
-4 -11
-8 -11
4 7
-8 -5
34 9
18 7
20 1
-12 -11
-30 -23
-42 -13
-24 -3
16 11
-16 -7
-24 -21
2 -9
28 11
6 -9
-22 -11
4 -7
28 7
-36 -15
-20 -21
4 11
-8 5
20 5
30 21
58 19
4 -1
-46 -19
-6 3
2 11
46 15
18 -1
-24 -7
-2...

output:

1

result:

wrong answer 1st lines differ - expected: '4', found: '1'

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%