oj.uz

Submission #234123

# Submission time Handle Problem Language Result Execution time Memory
234123 2020-05-23T08:35:21 Z anubhavdhar Mountains (NOI20_mountains) C++14
66 / 100
 193 ms 9848 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
{
	int 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 7 ms 4992 KB Output is correct
2 Correct 187 ms 9848 KB Output is correct
3 Correct 189 ms 9848 KB Output is correct
4 Correct 183 ms 9728 KB Output is correct
5 Correct 186 ms 9728 KB Output is correct
6 Correct 186 ms 9728 KB Output is correct
7 Correct 191 ms 9728 KB Output is correct
8 Correct 190 ms 9728 KB Output is correct
9 Correct 193 ms 9848 KB Output is correct
10 Correct 190 ms 9728 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 9728 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 8 ms 5120 KB Output is correct
2 Correct 9 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 8 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct

Subtask #5
28.0 / 28.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 187 ms 9848 KB Output is correct
3 Correct 189 ms 9848 KB Output is correct
4 Correct 183 ms 9728 KB Output is correct
5 Correct 186 ms 9728 KB Output is correct
6 Correct 186 ms 9728 KB Output is correct
7 Correct 191 ms 9728 KB Output is correct
8 Correct 190 ms 9728 KB Output is correct
9 Correct 193 ms 9848 KB Output is correct
10 Correct 190 ms 9728 KB Output is correct
11 Incorrect 168 ms 9728 KB Output isn't correct
12 Halted 0 ms 0 KB -