/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 6ms 6.566 MiB
#2 Accepted 6ms 6.562 MiB
#3 Accepted 7ms 6.578 MiB
#4 Wrong Answer 85ms 9.176 MiB
#5 Wrong Answer 86ms 9.176 MiB

Code

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

const int N = 1e5 + 7;
const ll inf = 1e17;
int n;
ll a[N];
struct st{
	#define lc (node << 1)
	#define rc ((node << 1) + 1)

	ll segT[N * 4], lazy[N * 4];
	st(){
		memset(segT, 0, sizeof(segT));
		memset(lazy, 0, sizeof(lazy));
	}

	inline void push(int node, int b, int e){
		if( lazy[node] == inf ) return;
		segT[node] = min(segT[node], lazy[node]);
		if ( b != e ) {
			lazy[lc] = min(lazy[node], lazy[lc]);
			lazy[rc] = min(lazy[node], lazy[rc]);
		}
		lazy[node] = inf;
	}

	inline ll combine(ll a, ll b){
		return min(a, b);
	}

	inline void pull(int node){
		segT[node] = min(segT[lc],  segT[rc]);
	}

	void build(int node, int b, int e){
		lazy[node] = inf;

		if(b == e){
			segT[node] = a[b];
			return;
		}

		int mid = (b + e) >> 1;
		build(lc, b, mid);
		build(rc, mid + 1, e);
		pull(node);
	}
	void upd(int node, int b, int e, int i, int j, ll val){
		push(node, b, e);
		if(b > j || e < i){
			return;
		}
		if(b >= i && e <= j){
			lazy[node] = val;
			push(node, b, e);
			return;
		}

		int mid = (b + e) >> 1; 
		upd(lc, b, mid, i, j, val);                   
		upd(rc, mid + 1, e, i, j, val);
		pull(node);                   
	}
	ll query(int node, int b, int e, int i, int j){
		push(node, b, e);
		if(b > j || e < i){
			return inf;
		}
		if(b >= i && e <= j){
			return segT[node];
		}

		int mid = (b + e) >> 1; 
		return combine(query(lc, b, mid, i , j), query(rc, mid + 1, e, i, j));                      
	}
}segT;
void solve()
{
    cin >> n;
    string s; cin >> s;

    vector<ll> r(n + 1), c(n + 1);

    for(int i = 1; i <= n; i++){
    	a[i] = inf;
    	cin >> r[i];
    }
    for(int i = 1; i <= n; i++){
    	cin >> c[i];
    }
    //cout << s << endl;
    segT.build(1, 1, n);
    //cout << s << endl;
    for(int i = 1; i <= n; i++){
    	int L = i, R = r[i];

    	ll val = c[i];

    	segT.upd(1, 1, n, L, R, val); 
    }
    //cout << s << endl;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
    	if(s[i - 1] == '1'){
    		ll tmp = segT.query(1, 1, n, i, i);
    		ans += tmp;
    	}
    }
    //cout << s << endl;
    cout << ans << '\n';

}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1, tc = 0;
    //cin >> t;

    while(t--){
    	//cout << "Case " << ++tc << ": ";
    	solve();
    } 
}


Information

Submit By
Type
Submission
Problem
P1125 Lumina's Light-Out Challenge
Contest
Sylhet ICPC 2024 Collaborative Challenge: Episode 2
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-30 10:55:11
Judged At
2024-11-11 02:35:02
Judged By
Score
0
Total Time
86ms
Peak Memory
9.176 MiB