oj.uz

Submission #569891

# Submission time Handle Problem Language Result Execution time Memory
569891 2022-05-28T04:33:00 Z jrodsc Mountains (NOI20_mountains) C++17
4 / 100
 238 ms 77444 KB 
#include <bits/stdc++.h>
#define INF 1000000000
#define ll long long
#define MAX_N 30

using namespace std;

struct SegmentTree{
	ll s = 0;
	
	SegmentTree * left = NULL, * right = NULL;
	
	SegmentTree(int l,int r,vector<int> &a){
		if(l == r){
			s = (ll)a[l];
		}else{
			int mid = (l+r)/2;
			left = new SegmentTree(l,mid,a);
			right = new SegmentTree(mid+1,r,a);
			
			s = left->s + right->s;
		}
	}
	
	void upd(int l,int r,int p,int k){
		if(l == p && r == p){
			s += k;
			//cout << l << ' ' << r << ' ' << s << endl;
		}
		else{
			int mid = (l+r)/2;
			if(p <= mid)
				left->upd(l,mid,p,k);
			else
				right->upd(mid+1,r,p,k);
			
			s = left->s + right->s;
		}
	}
	
	ll rsq(int l,int r,int ss,int e){
		if(l >= ss && r <= e)
			return s;
		else if(l > e || r < ss)
			return 0;
		else{
			int mid = (l+r)/2;
			return left->rsq(l,mid,ss,e) + right->rsq(mid+1,r,ss,e);
		}
	}
};

int main(){	
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	
	cin >> n;
	
	ll h[n];
	
	set<ll> s;
	map<ll,int> trlt;
	for(int i = 0; i < n; i++){
		cin >> h[i];
		s.insert(h[i]);
	}
	
	int c = 0;
	for(auto x : s){
		trlt[x] = c++;
	}
	
	for(int i = 0; i < n; i++){
		h[i] = trlt[h[i]];
	}
	
	vector<int> a(MAX_N+1,0);
	
	SegmentTree st_left(0,MAX_N,a);
	
	for(int i = 0; i < n; i++){
		a[h[i]]++;
	}
	
	SegmentTree st_right(0,MAX_N,a);
	
	st_left.upd(0,MAX_N,h[0],1);
	st_right.upd(0,MAX_N,h[0],-1);
	st_right.upd(0,MAX_N,h[1],-1);
	
	ll ans = 0;
	
	for(int i = 1; i < n-1; i++){
		if(h[i] > 0) ans += st_left.rsq(0,MAX_N,0,h[i]-1) * st_right.rsq(0,MAX_N,0,h[i]-1);
		st_left.upd(0,MAX_N,h[i],1);
		st_right.upd(0,MAX_N,h[i+1],-1);
	}
	
	cout << ans << endl;
	
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 238 ms 77444 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3284 KB Output is correct
2 Correct 49 ms 3172 KB Output is correct
3 Correct 52 ms 3144 KB Output is correct
4 Correct 37 ms 3164 KB Output is correct
5 Correct 37 ms 3260 KB Output is correct
6 Correct 38 ms 3284 KB Output is correct
7 Correct 41 ms 3232 KB Output is correct
8 Correct 34 ms 3272 KB Output is correct
9 Correct 38 ms 3232 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3284 KB Output is correct
2 Correct 49 ms 3172 KB Output is correct
3 Correct 52 ms 3144 KB Output is correct
4 Correct 37 ms 3164 KB Output is correct
5 Correct 37 ms 3260 KB Output is correct
6 Correct 38 ms 3284 KB Output is correct
7 Correct 41 ms 3232 KB Output is correct
8 Correct 34 ms 3272 KB Output is correct
9 Correct 38 ms 3232 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Runtime error 41 ms 5964 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3284 KB Output is correct
2 Correct 49 ms 3172 KB Output is correct
3 Correct 52 ms 3144 KB Output is correct
4 Correct 37 ms 3164 KB Output is correct
5 Correct 37 ms 3260 KB Output is correct
6 Correct 38 ms 3284 KB Output is correct
7 Correct 41 ms 3232 KB Output is correct
8 Correct 34 ms 3272 KB Output is correct
9 Correct 38 ms 3232 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Runtime error 41 ms 5964 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 238 ms 77444 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -