QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#840314#8712. Flooding Wallzhassyn#0 2ms9732kbC++204.6kb2025-01-02 17:02:302025-01-02 17:02:37

Judging History

This is the latest submission verdict.

  • [2025-01-02 17:02:37]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 9732kb
  • [2025-01-02 17:02:30]
  • 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 = 2 * 1e5 + 100, M = 4096 + 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 a[N], b[N], num[N], n, p[N];
void subtask1(){
	ll ans = 0;
	for(ll mask = 0; mask < (1 << n); mask++){
		for(ll dig = 0; dig < n; dig++){
			if((mask & (1 << dig)) > 0) num[dig] = a[dig];
			else num[dig] = b[dig];
		}
		vector <pll> vec;
		// for(ll i = 0; i < n; i++){
			// cout << num[i] << " ";
		// }
		// cout << endl;
		for(ll i = 0; i < n; i++){
			ll res = 0, last = -1, cnt = 0;
			while((ll)vec.size() != 0){
				pll v = vec.back();
				if(v.F <= num[i]){
					cnt += v.S;
					last = v.F;
					res += um(num[i] - v.F, v.S);
					vec.pop_back();
				} else break;
			}
			if((ll)vec.size() != 0) ans += res;
			else ans = ans + subr(res, um(cnt, num[i] - last));
			ans %= mod;
			vec.pb({num[i], cnt + 1});
		}
		//cout << ans << " HERE\n";
	}
	cout << ans;
}
// pll sf[N], pr[N];
// ll ls[N], rs[N], fen[N], was[N];
// bool wb[N];
// void upd(ll i, ll delta){
	// for(; i < N; i = (i | (i+  1))){
		// fen[i] += delta;
	// }
// }
// ll get(ll r){
	// ll res = 0;
	// for(; r >= 0; r = (r & (r + 1)) - 1){
		// res += fen[r];
	// }
	// return res;
// }
// void subtask2(){
	// ll ans = 0;
	// for(ll i = 0; i < n; i++){
		// //cout << i << " INDEX\n";
		// set <pll> mn;
		// // This shit is not for me
		// for(ll j = 1; j <= 1000; j++){
			// was[j] = 0;
			// wb[j] = 0;
		// }
		// for(ll j = i + 1; j < n; j++){
			// mn.insert({-b[j], j});
			// upd(a[j], 1);
		// }
		// for(ll j = i + 1; j < n; j++){
			// mn.erase({-b[j], j});
			// upd(a[j], -1);
			// ll mini = 0;
			// if((int)mn.size() != 0) mini = -mn.begin()->F;
			// if(mini > a[j]) sf[j].F = 0;
			// else sf[j].F = p[get(a[j]) - was[a[j]]];
// 			
			// if(mini > b[j] || wb[b[j]]) sf[j].S = 0;
			// else sf[j].S = p[get(b[j]) - was[b[j]]];
			// //cout << sf[j].F << " "<< sf[j].S << endl;
			// upd(a[j], 1);
			// was[a[j]]++;
			// wb[b[j]] = 1;
			// mn.insert({-b[j], j});
		// }
		// for(ll j = i + 1; j < n; j++){
			// rs[a[j]] += sf[j].F;
			// rs[a[j]] %= mod;
			// rs[b[j]] += sf[j].S;
			// rs[b[j]] %= mod;
// 			
			// upd(a[j], -1);
		// }
// 		
		// mn.clear();
		// // bless you/ work please
		// for(ll j = 1; j <= 1000; j++){
			// was[j] = 0;
			// wb[j] = 0;
		// }
		// for(ll j = i - 1; j >= 0; j--){
			// mn.insert({-b[j], j});
			// upd(a[j], 1);
		// }
		// for(ll j = i - 1; j >= 0; j--){
			// mn.erase({-b[j], j});
			// upd(a[j], -1);
			// ll mini = 0;
			// if((int)mn.size() != 0) mini = -mn.begin()->F;
			// if(mini > a[j]) pr[j].F = 0;
			// else pr[j].F = p[get(a[j]) - was[a[j]]];
// 			
			// if(mini > b[j] || wb[b[j]]) pr[j].S = 0;
			// else pr[j].S = p[get(b[j]) - was[b[j]]];
			// //cout << pr[j].F << " "<< pr[j].S << endl;
			// upd(a[j], 1);
			// was[a[j]]++;
			// wb[b[j]] = true;
			// mn.insert({-b[j], j});
		// }
		// for(ll j = i - 1; j >= 0; j--){
			// ls[a[j]] += pr[j].F;
			// ls[a[j]] %= mod;
			// ls[b[j]] += pr[j].S;
			// ls[b[j]] %= mod;
// 			
			// upd(a[j], -1);
		// }
		// for(ll j = 1; j <= 1000; j++){
			// for(ll k = 1; k <= 1000; k++){
				// if(a[i] < min(k, j)) ans += um(min(k, j) - a[i], um(rs[j], ls[k]));
				// if(b[i] < min(k, j)) ans += um(min(k, j) - b[i], um(rs[j], ls[k]));
				// ans %= mod;
			// }
		// }
		// for(ll j = 1; j <= 1000; j++){
			// rs[j] = ls[j] = 0;
		// }
		// //cout << ans << " RESULT\n";
	// }
	// cout << ans;
// }
ll pref[N];
void subtask5(){
	ll cnt = 0, sm = 1, ans = 0;
	for(ll i = 1; i <= n; i++){
		cnt++;
		pref[i] = pref[i - 1] + um(cnt, sm);
		pref[i] %= mod;
		sm = um(sm, 2LL);
		//cout << pref[i] << " ";
	}
	//cout << endl;
	for(ll i = 1; i < n; i++){
		ans += pref[n - i - 1];
		ans %= mod;
	}
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	p[0] = 1;
	ll mx = 0;
	for(ll i = 1; i <= n; i++){
		p[i] = um(p[i - 1], 2LL);
	}
	for(ll i = 0; i < n; i++){
		cin >> a[i];
	}
	for(ll i = 0; i < n; i++){
		cin >> b[i];
		if(b[i] > a[i]) swap(a[i], b[i]);
		mx = max(mx, a[i]);
	}
	// if(n <= 20){
		// subtask1();
		// return 0;
	// }
	if(mx <= 2){
		subtask5();
		return 0;
	}
	//subtask2();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 2ms
memory: 9728kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

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

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:


result:

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

Subtask #2:

score: 0
Wrong Answer

Test #23:

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

input:

100
948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...

output:


result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Runtime Error

Test #57:

score: 0
Runtime Error

input:

500000
1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%