oj.uz

Submission #285592

# Submission time Handle Problem Language Result Execution time Memory
285592 2020-08-29T10:01:23 Z Ronin13 Mountains (NOI20_mountains) C++14
24 / 100
 809 ms 67864 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
 
using namespace std;

int n;
int a[300001];
vector<int>t[1200001];

void build(int v,int l,int r){
	if(l==r){
		t[v].pb(a[l]);
		return;
	}
	int m=(l+r)/2;
	build(2*v,l,m);
	build(2*v+1,m+1,r);
	t[v].resize((int)t[2*v].size()+(int)t[2*v+1].size());
	merge(t[2*v].begin(),t[2*v].end(),t[2*v+1].begin(),t[2*v+1].end(),t[v].begin());
}

ll get(int v,int l,int r,int tl,int tr,int val){
	if(l==tl&&r==tr){
		ll k=lower_bound(t[v].begin(),t[v].end(),val)-t[v].begin();
		return k;
	}
	int tm=(tl+tr)/2;
	if(r<=tm)return get(2*v,l,r,tl,tm,val);
	if(l>tm)return get(2*v+1,l,r,tm+1,tr,val);
	return get(2*v,l,tm,tl,tm,val)+get(2*v+1,tm+1,r,tm+1,tr,val);
}

ll ans=0;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=2;i<n;i++){
		ans+=get(1,1,i-1,1,n,a[i])*get(1,i+1,n,1,n,a[i]);
	}
	cout<<ans;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 334 ms 64760 KB Output is correct
3 Correct 325 ms 64760 KB Output is correct
4 Correct 308 ms 64960 KB Output is correct
5 Correct 323 ms 64888 KB Output is correct
6 Correct 331 ms 64884 KB Output is correct
7 Correct 310 ms 64892 KB Output is correct
8 Correct 323 ms 64888 KB Output is correct
9 Correct 309 ms 64760 KB Output is correct
10 Correct 315 ms 64884 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 66552 KB Output is correct
2 Correct 395 ms 66684 KB Output is correct
3 Correct 393 ms 66680 KB Output is correct
4 Correct 396 ms 66680 KB Output is correct
5 Correct 391 ms 66552 KB Output is correct
6 Correct 396 ms 66756 KB Output is correct
7 Correct 402 ms 66560 KB Output is correct
8 Correct 412 ms 66684 KB Output is correct
9 Correct 376 ms 66552 KB Output is correct
10 Correct 20 ms 28544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 66552 KB Output is correct
2 Correct 395 ms 66684 KB Output is correct
3 Correct 393 ms 66680 KB Output is correct
4 Correct 396 ms 66680 KB Output is correct
5 Correct 391 ms 66552 KB Output is correct
6 Correct 396 ms 66756 KB Output is correct
7 Correct 402 ms 66560 KB Output is correct
8 Correct 412 ms 66684 KB Output is correct
9 Correct 376 ms 66552 KB Output is correct
10 Correct 20 ms 28544 KB Output is correct
11 Correct 648 ms 66824 KB Output is correct
12 Correct 653 ms 66936 KB Output is correct
13 Correct 666 ms 66936 KB Output is correct
14 Correct 656 ms 66952 KB Output is correct
15 Correct 647 ms 66988 KB Output is correct
16 Correct 682 ms 66936 KB Output is correct
17 Correct 651 ms 66936 KB Output is correct
18 Correct 378 ms 66936 KB Output is correct
19 Correct 383 ms 66936 KB Output is correct
20 Correct 20 ms 28544 KB Output is correct

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 66552 KB Output is correct
2 Correct 395 ms 66684 KB Output is correct
3 Correct 393 ms 66680 KB Output is correct
4 Correct 396 ms 66680 KB Output is correct
5 Correct 391 ms 66552 KB Output is correct
6 Correct 396 ms 66756 KB Output is correct
7 Correct 402 ms 66560 KB Output is correct
8 Correct 412 ms 66684 KB Output is correct
9 Correct 376 ms 66552 KB Output is correct
10 Correct 20 ms 28544 KB Output is correct
11 Correct 648 ms 66824 KB Output is correct
12 Correct 653 ms 66936 KB Output is correct
13 Correct 666 ms 66936 KB Output is correct
14 Correct 656 ms 66952 KB Output is correct
15 Correct 647 ms 66988 KB Output is correct
16 Correct 682 ms 66936 KB Output is correct
17 Correct 651 ms 66936 KB Output is correct
18 Correct 378 ms 66936 KB Output is correct
19 Correct 383 ms 66936 KB Output is correct
20 Correct 20 ms 28544 KB Output is correct
21 Correct 809 ms 67864 KB Output is correct
22 Correct 792 ms 67836 KB Output is correct
23 Correct 795 ms 67812 KB Output is correct
24 Correct 794 ms 67832 KB Output is correct
25 Correct 802 ms 67860 KB Output is correct
26 Correct 807 ms 67756 KB Output is correct
27 Correct 790 ms 67704 KB Output is correct
28 Correct 438 ms 67704 KB Output is correct
29 Correct 439 ms 67832 KB Output is correct
30 Correct 20 ms 28544 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 334 ms 64760 KB Output is correct
3 Correct 325 ms 64760 KB Output is correct
4 Correct 308 ms 64960 KB Output is correct
5 Correct 323 ms 64888 KB Output is correct
6 Correct 331 ms 64884 KB Output is correct
7 Correct 310 ms 64892 KB Output is correct
8 Correct 323 ms 64888 KB Output is correct
9 Correct 309 ms 64760 KB Output is correct
10 Correct 315 ms 64884 KB Output is correct
11 Correct 398 ms 66552 KB Output is correct
12 Correct 395 ms 66684 KB Output is correct
13 Correct 393 ms 66680 KB Output is correct
14 Correct 396 ms 66680 KB Output is correct
15 Correct 391 ms 66552 KB Output is correct
16 Correct 396 ms 66756 KB Output is correct
17 Correct 402 ms 66560 KB Output is correct
18 Correct 412 ms 66684 KB Output is correct
19 Correct 376 ms 66552 KB Output is correct
20 Correct 20 ms 28544 KB Output is correct
21 Correct 648 ms 66824 KB Output is correct
22 Correct 653 ms 66936 KB Output is correct
23 Correct 666 ms 66936 KB Output is correct
24 Correct 656 ms 66952 KB Output is correct
25 Correct 647 ms 66988 KB Output is correct
26 Correct 682 ms 66936 KB Output is correct
27 Correct 651 ms 66936 KB Output is correct
28 Correct 378 ms 66936 KB Output is correct
29 Correct 383 ms 66936 KB Output is correct
30 Correct 20 ms 28544 KB Output is correct
31 Incorrect 20 ms 28544 KB Output isn't correct
32 Halted 0 ms 0 KB -