oj.uz

답안 #234121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234121 2020-05-23T08:33:11 Z anubhavdhar Mountains (NOI20_mountains) C++14
66 / 100
 195 ms 15352 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 184 ms 15224 KB Output is correct
3 Correct 194 ms 15224 KB Output is correct
4 Correct 189 ms 15224 KB Output is correct
5 Correct 188 ms 15312 KB Output is correct
6 Correct 187 ms 15352 KB Output is correct
7 Correct 184 ms 15264 KB Output is correct
8 Correct 191 ms 15228 KB Output is correct
9 Correct 195 ms 15224 KB Output is correct
10 Correct 191 ms 15352 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 10368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 10368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 9 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 9 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 9 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 9 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Correct 15 ms 5376 KB Output is correct
12 Correct 15 ms 5376 KB Output is correct
13 Correct 15 ms 5376 KB Output is correct
14 Correct 15 ms 5376 KB Output is correct
15 Correct 16 ms 5376 KB Output is correct
16 Correct 15 ms 5376 KB Output is correct
17 Correct 15 ms 5376 KB Output is correct
18 Correct 15 ms 5352 KB Output is correct
19 Correct 14 ms 5248 KB Output is correct
20 Correct 8 ms 4992 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 10368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 184 ms 15224 KB Output is correct
3 Correct 194 ms 15224 KB Output is correct
4 Correct 189 ms 15224 KB Output is correct
5 Correct 188 ms 15312 KB Output is correct
6 Correct 187 ms 15352 KB Output is correct
7 Correct 184 ms 15264 KB Output is correct
8 Correct 191 ms 15228 KB Output is correct
9 Correct 195 ms 15224 KB Output is correct
10 Correct 191 ms 15352 KB Output is correct
11 Incorrect 166 ms 10368 KB Output isn't correct
12 Halted 0 ms 0 KB -