oj.uz

Submission #234126

# Submission time Handle Problem Language Result Execution time Memory
234126 2020-05-23T08:42:19 Z anubhavdhar Mountains (NOI20_mountains) C++14
66 / 100
 193 ms 14584 KB 
#include<bits/stdc++.h>
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
 
const short int __PRECISION = 10;
 
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 3e5+5;
const ll ROOTN = 320;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
 
struct SegTree
{
	ll st[4*MAXN];
 
	void upd(int node, int ss, int se, int i)
	{
		if(ss >  i or se < i)
			return;
		if(ss == se)
		{
			++st[node];
			return;
		}
		int mid = (ss + se)/2;
		upd(node*2 + 1, ss, mid, i);
		upd(node*2 + 2, mid+1, se, i);
		st[node] = st[node*2+1] + st[node*2+2];
	}
 
	ll quer(int node, int ss, int se, int l, int r)
	{
		if(ss > r or se < l)	return 0;
		if(ss >= l and se <= r)	return st[node];
		int mid = (ss + se) / 2;
		return quer(node*2+1, ss, mid,l,r) + quer(node*2+2,mid+1,se,l,r);
	}
 
	SegTree()
	{
		F0R(i, 4*MAXN)
			st[i] = 0;
	}
 
	inline void update(int i)
	{
		upd(0, 0, MAXN, i);
	}
 
	inline ll query(int i, int ded)
	{
		ll a = quer(0, 0, MAXN, 0, i-1) - ded, b = quer(0, 0, MAXN, i+1, MAXN);
		// cout<<"a = "<<a<<", b = "<<b<<'\n';
		return (a*b);
	}
} S;
 
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin>>N;
	pair<ll, int> A[N];
	F0R(i, N)
	{
		ll j;
		cin>>j;
		A[i] = mp(j, i+1);
	}
	sort(A, A + N);
	ll previo = -1, tot = 0, ans = 0;
	F0R(i, N)
	{
		// cout<<"for ("<<A[i].ff<<','<<A[i].ss<<") : ";
		if(A[i].ff != previo)
			tot = 0;
		S.update(A[i].ss);
		int tmp = S.query(A[i].ss, tot);
		// cout<<"tot = "<<tot<<", previo = "<<previo<<", no. of combinations is "<<tmp<<'\n';
		previo = A[i].ff;
		++tot;
		ans += tmp;
	}
	cout<<ans;
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 187 ms 14464 KB Output is correct
3 Correct 190 ms 14464 KB Output is correct
4 Correct 187 ms 14464 KB Output is correct
5 Correct 188 ms 14464 KB Output is correct
6 Correct 190 ms 14464 KB Output is correct
7 Correct 184 ms 14464 KB Output is correct
8 Correct 185 ms 14464 KB Output is correct
9 Correct 189 ms 14464 KB Output is correct
10 Correct 193 ms 14464 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct
8 Correct 11 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct
8 Correct 11 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 17 ms 9856 KB Output is correct
12 Correct 18 ms 9856 KB Output is correct
13 Correct 17 ms 9856 KB Output is correct
14 Correct 20 ms 9856 KB Output is correct
15 Correct 18 ms 9856 KB Output is correct
16 Correct 17 ms 9856 KB Output is correct
17 Correct 17 ms 9856 KB Output is correct
18 Correct 17 ms 9856 KB Output is correct
19 Correct 16 ms 9856 KB Output is correct
20 Correct 9 ms 9728 KB Output is correct

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 187 ms 14464 KB Output is correct
3 Correct 190 ms 14464 KB Output is correct
4 Correct 187 ms 14464 KB Output is correct
5 Correct 188 ms 14464 KB Output is correct
6 Correct 190 ms 14464 KB Output is correct
7 Correct 184 ms 14464 KB Output is correct
8 Correct 185 ms 14464 KB Output is correct
9 Correct 189 ms 14464 KB Output is correct
10 Correct 193 ms 14464 KB Output is correct
11 Incorrect 165 ms 14584 KB Output isn't correct
12 Halted 0 ms 0 KB -