oj.uz

Submission #307115

# Submission time Handle Problem Language Result Execution time Memory
307115 2020-09-27T06:34:48 Z Hemimor Mountains (NOI20_mountains) C++14
24 / 100
 472 ms 14348 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

vi vin(int n,int d=0){
	vi a(n);
	for(auto &i:a){
		cin>>i;
		i-=d;
	}
	return a;
}

vl vln(int n,int d=0){
	vl a(n);
	for(auto &i:a){
		cin>>i;
		i-=d;
	}
	return a;
}

vvi gin(int n,int m,int d=1){
	vvi g(n);
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u-=d,v-=d;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return g;
}

void vout(vi a){
	int n=a.size();
	cout<<n<<" :";
	for(auto i:a) cout<<' '<<i;
	cout<<endl;
}

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=0;
		while(a<b){
			if(a%2==0) m+=date[a++];
			if(b%2==0) m+=date[--b];
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

int n;
vi a;

vi f(){
	Segment_Tree st(n);
	vi b(n);
	for(int i=0;i<n;i++){
		b[i]=st.Query(0,a[i]);
		st.Update(a[i],1);
	}
	reverse(a.begin(),a.end());
	return b;
}

int main(){
	cin>>n;
	a=vin(n);
	vi b=a;
	sort(b.begin(),b.end());
	map<int,int> mp;
	for(int i=0;i<n;i++) mp[b[i]]=i;
	for(int i=0;i<n;i++) a[i]=mp[a[i]];
	b=f();
	vi c=f();
	ll res=0;
	for(int i=0;i<n;i++) res+=(ll)b[i]*c[n-i-1];
	cout<<res<<endl;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 70 ms 7936 KB Output is correct
3 Correct 71 ms 7940 KB Output is correct
4 Correct 72 ms 7936 KB Output is correct
5 Correct 72 ms 7936 KB Output is correct
6 Correct 72 ms 8064 KB Output is correct
7 Correct 72 ms 7936 KB Output is correct
8 Correct 72 ms 7936 KB Output is correct
9 Correct 73 ms 8056 KB Output is correct
10 Correct 71 ms 7936 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8580 KB Output is correct
2 Correct 151 ms 8568 KB Output is correct
3 Correct 154 ms 8564 KB Output is correct
4 Correct 153 ms 8568 KB Output is correct
5 Correct 152 ms 8672 KB Output is correct
6 Correct 156 ms 8676 KB Output is correct
7 Correct 153 ms 8568 KB Output is correct
8 Correct 145 ms 8568 KB Output is correct
9 Correct 145 ms 8672 KB Output is correct
10 Correct 1 ms 256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8580 KB Output is correct
2 Correct 151 ms 8568 KB Output is correct
3 Correct 154 ms 8564 KB Output is correct
4 Correct 153 ms 8568 KB Output is correct
5 Correct 152 ms 8672 KB Output is correct
6 Correct 156 ms 8676 KB Output is correct
7 Correct 153 ms 8568 KB Output is correct
8 Correct 145 ms 8568 KB Output is correct
9 Correct 145 ms 8672 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 215 ms 8840 KB Output is correct
12 Correct 214 ms 8824 KB Output is correct
13 Correct 217 ms 8952 KB Output is correct
14 Correct 216 ms 8824 KB Output is correct
15 Correct 215 ms 8928 KB Output is correct
16 Correct 215 ms 8824 KB Output is correct
17 Correct 214 ms 8824 KB Output is correct
18 Correct 173 ms 8952 KB Output is correct
19 Correct 174 ms 8956 KB Output is correct
20 Correct 1 ms 256 KB Output is correct

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 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 154 ms 8580 KB Output is correct
2 Correct 151 ms 8568 KB Output is correct
3 Correct 154 ms 8564 KB Output is correct
4 Correct 153 ms 8568 KB Output is correct
5 Correct 152 ms 8672 KB Output is correct
6 Correct 156 ms 8676 KB Output is correct
7 Correct 153 ms 8568 KB Output is correct
8 Correct 145 ms 8568 KB Output is correct
9 Correct 145 ms 8672 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 215 ms 8840 KB Output is correct
12 Correct 214 ms 8824 KB Output is correct
13 Correct 217 ms 8952 KB Output is correct
14 Correct 216 ms 8824 KB Output is correct
15 Correct 215 ms 8928 KB Output is correct
16 Correct 215 ms 8824 KB Output is correct
17 Correct 214 ms 8824 KB Output is correct
18 Correct 173 ms 8952 KB Output is correct
19 Correct 174 ms 8956 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 472 ms 14348 KB Output is correct
22 Correct 463 ms 14328 KB Output is correct
23 Correct 446 ms 14296 KB Output is correct
24 Correct 460 ms 14176 KB Output is correct
25 Correct 450 ms 14200 KB Output is correct
26 Correct 457 ms 14200 KB Output is correct
27 Correct 448 ms 14316 KB Output is correct
28 Correct 315 ms 14328 KB Output is correct
29 Correct 312 ms 14200 KB Output is correct
30 Correct 1 ms 384 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 70 ms 7936 KB Output is correct
3 Correct 71 ms 7940 KB Output is correct
4 Correct 72 ms 7936 KB Output is correct
5 Correct 72 ms 7936 KB Output is correct
6 Correct 72 ms 8064 KB Output is correct
7 Correct 72 ms 7936 KB Output is correct
8 Correct 72 ms 7936 KB Output is correct
9 Correct 73 ms 8056 KB Output is correct
10 Correct 71 ms 7936 KB Output is correct
11 Correct 154 ms 8580 KB Output is correct
12 Correct 151 ms 8568 KB Output is correct
13 Correct 154 ms 8564 KB Output is correct
14 Correct 153 ms 8568 KB Output is correct
15 Correct 152 ms 8672 KB Output is correct
16 Correct 156 ms 8676 KB Output is correct
17 Correct 153 ms 8568 KB Output is correct
18 Correct 145 ms 8568 KB Output is correct
19 Correct 145 ms 8672 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 215 ms 8840 KB Output is correct
22 Correct 214 ms 8824 KB Output is correct
23 Correct 217 ms 8952 KB Output is correct
24 Correct 216 ms 8824 KB Output is correct
25 Correct 215 ms 8928 KB Output is correct
26 Correct 215 ms 8824 KB Output is correct
27 Correct 214 ms 8824 KB Output is correct
28 Correct 173 ms 8952 KB Output is correct
29 Correct 174 ms 8956 KB Output is correct
30 Correct 1 ms 256 KB Output is correct
31 Incorrect 1 ms 384 KB Output isn't correct
32 Halted 0 ms 0 KB -