oj.uz

Submission #945670

# Submission time Handle Problem Language Result Execution time Memory
945670 2024-03-14T06:13:03 Z yhkhoo Fancy Fence (CEOI20_fancyfence) C++17
25 / 100
 36 ms 11160 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;

const int MOD = 1000000007;

#define lsb(x) ((x) & (-x))

int n;
const int MAXN = 100005;
int fw[MAXN];

void update(int X, int V){
	X++;
	while(X<=n){
		fw[X] += V;
		X += lsb(X);
	}
}

int query(int R){
	R++;
	if(R==0) return 0;
	int result = 0;
	while(R){
		result += fw[R];
		R -= lsb(R);
	}
	return result;
}

inline int goat(int n, int m){
	if(n <= 0 || m <= 0) return 0;
	int x = (n%MOD)*((n+1)%MOD);
	x >>= 1;
	int y = (m%MOD)*((m+1)%MOD);
	y >>= 1;
	return (x*y)%MOD;
}

signed main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n;
	vector<int> h(n), w(n), wp(n);
	vector<pii> hs;
	hs.reserve(n);
	for(int i=0; i<n; i++){
		cin >> h[i];
		hs.emplace_back(h[i], i);
	}
	for(int i=0; i<n; i++){
		cin >> w[i];
		if(i==0) wp[0] = w[0];
		else wp[i] = wp[i-1]+w[i];
	}
	sort(hs.begin(), hs.end());
	set<int> dead;
	dead.insert(-1);
	dead.insert(n);
	int ans=0;
	for(int i=0; i<n; i++){
		auto[ch, cs] = hs[i];
		int cph = query(cs);
		if(cph == ch){
			dead.insert(cs);
			continue;
		}
		auto pr = dead.upper_bound(cs);
		auto pl = pr;
		pl--;
		int cfr = (*pr)-1, cfl = (*pl)+1;
		int cfw = wp[cfr];
		if(cfl > 0) cfw -= wp[cfl-1];
		int uh = ch-cph;
		ans += goat(ch, cfw);
		ans -= goat(cph, cfw);
		update(cfl, uh);
		update(cfr+1, -uh);
		dead.insert(cs);
		ans += MOD;
		ans %= MOD;
	}
	cout << ans;
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 21 ms 5724 KB Output is correct
4 Correct 35 ms 10836 KB Output is correct
5 Correct 36 ms 10836 KB Output is correct
6 Correct 34 ms 11160 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -