QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#840075#8712. Flooding Wallzhassyn#0 398ms16072kbC++203.8kb2025-01-02 15:22:372025-01-02 15:22:38

Judging History

This is the latest submission verdict.

  • [2025-01-02 15:22:38]
  • Judged
  • Verdict: 0
  • Time: 398ms
  • Memory: 16072kb
  • [2025-01-02 15:22:37]
  • 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;
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], p[N], fen[N], was[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;
		}
		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]) 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]]++;
			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;
		}
		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]) 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]]++;
			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;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	p[0] = 1;
	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]);
	}
	// if(n <= 20){
		// subtask1();
		// return 0;
	// }
	subtask2();
  return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 8
Accepted
time: 23ms
memory: 13796kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 8
Accepted
time: 60ms
memory: 15840kb

input:

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

output:

21116

result:

ok single line: '21116'

Test #3:

score: 8
Accepted
time: 8ms
memory: 9996kb

input:

1
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 8
Accepted
time: 11ms
memory: 15912kb

input:

2
1 1
2 2

output:

0

result:

ok single line: '0'

Test #5:

score: 8
Accepted
time: 21ms
memory: 15832kb

input:

3
1 1 1
2 2 2

output:

1

result:

ok single line: '1'

Test #6:

score: 8
Accepted
time: 17ms
memory: 15848kb

input:

3
1 1 1
3 2 3

output:

3

result:

ok single line: '3'

Test #7:

score: 8
Accepted
time: 14ms
memory: 16072kb

input:

3
2 1 1
3 2 3

output:

4

result:

ok single line: '4'

Test #8:

score: 8
Accepted
time: 17ms
memory: 11788kb

input:

3
1 1 2
3 2 3

output:

4

result:

ok single line: '4'

Test #9:

score: 8
Accepted
time: 27ms
memory: 15852kb

input:

4
1 1 2 2
2 2 1 1

output:

6

result:

ok single line: '6'

Test #10:

score: 8
Accepted
time: 17ms
memory: 16056kb

input:

3
1 4 4
3 1 1

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Runtime Error

input:

20
801072306 297281669 94099424 745640358 822582129 579751930 776707816 425952653 529794053 256263083 615445445 401366545 990263003 967996508 788867983 916880116 837997768 346996508 623409388 122077161
141734988 448434751 822901346 825591177 388082644 468025968 260356829 1164654 537396602 730502935 ...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 17
Accepted
time: 393ms
memory: 15928kb

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:

164439470

result:

ok single line: '164439470'

Test #24:

score: 0
Wrong Answer
time: 398ms
memory: 13896kb

input:

99
426 562 392 187 480 118 86 459 941 159 104 108 323 616 104 679 464 929 60 387 335 298 540 352 520 152 76 233 69 50 422 839 236 113 79 782 44 253 791 857 393 767 297 267 23 523 274 514 489 58 217 361 408 753 990 491 787 529 759 351 668 348 811 737 764 672 471 115 815 701 604 348 708 512 227 707 20...

output:

167414504

result:

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

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%