oj.uz

Submission #105698

# Submission time Handle Problem Language Result Execution time Memory
105698 2019-04-14T04:14:37 Z Pro_ktmr 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 359 ms 16012 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

struct SegmentTree{
public:
	vector<int> node;
	int n;
	void reset(int N){
		node.clear();
		n = 1;
		while(n < N) n *= 2;
		for(int i=0; i<n*2-1; i++) node.push_back(0);
	}
	void update(int idx){
		node[n+idx-1] = 1;
		int tmp = n+idx-1;
		while(tmp > 0){
			tmp = (tmp-1) / 2;
			node[tmp]++;
		}
	}
	int countRtoL(int idx){ //idxより右側で左端に動いた個数
		return query(0, idx, n, 0, n);
	}
	int countLtoR(int idx){ //idxより右側で左端に動いた個数
		return query(0, 0, idx, 0, n);
	}
	int query(int now, int l, int r, int nowL, int nowR){
		if(nowR <= l || r <= nowL) return 0;
		if(l <= nowL && nowR <= r) return node[now];
		return query(now*2+1, l, r, nowL, (nowL+nowR)/2) + query(now*2+2, l, r, (nowL+nowR)/2, nowR);
	}
	void print(){
		int now = 0;
		int m = 1;
		for(int i=0; i<node.size(); i++){
			cout << node[i] << " ";
			now++;
			if(now == m){
				cout << endl;
				now = 0;
				m *= 2;
			}
		}
	}
};

int N;
vector<pair<int,int> > D;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	cin >> N;
	for(int i=0; i<N; i++){
		int d;
		cin >> d;
		D.push_back(MP(d,i));
	}
	sort(D.begin(), D.end());

	LL ans = 0;
	int l = 0; //移動させるならここ
	int r = N-1;
	SegmentTree stRtoL,stLtoR;
	stRtoL.reset(N);
	stLtoR.reset(N);
	for(int i=0; i<N; i++){
		if(i > 0 && D[i].first == D[i-1].first) continue;
		int now = D[i].second+stRtoL.countRtoL(D[i].second)-stLtoR.countLtoR(D[i].second);
		if(i==N-1 || D[i].first!=D[i+1].first){
			if(now-l <= r-now){
				ans += now-l;
				stRtoL.update(D[i].second);
				l++;
			}
			else{
				ans += r-now;
				stLtoR.update(D[i].second);
				r--;
			}
		}
		else{
			int c = upper_bound(D.begin(), D.end(), MP(D[i].first,INT_MAX)) - D.begin();
			//初期状態では全部左へ
			int L = l;
			int R = r;
			LL re = 0;
			for(int j=i; j<c; j++){
				int now2 = D[j].second+stRtoL.countRtoL(D[j].second)-stLtoR.countLtoR(D[j].second);
				re += now2-L;
				L++;
			}

			LL tmp = re;
			int pos = c;
			//cout << tmp << endl;
			for(int j=c-1; j>=i; j--){
				int now2 = D[j].second+stRtoL.countRtoL(D[j].second)-stLtoR.countLtoR(D[j].second);
				L--;
				tmp -= now2-L;
				tmp += R-now2;
				R--;
				//cout << tmp << endl;
				if(tmp < re){
					re = tmp;
					pos = j;
				}
			}
			//cout << re << " " << pos << endl;
			for(int j=i; j<pos; j++){
				int now2 = D[j].second+stRtoL.countRtoL(D[j].second)-stLtoR.countLtoR(D[j].second);
				ans += now2-l;
				stRtoL.update(D[j].second);
				l++;
				//cout << now2 << " " << ans << endl;
			}
			for(int j=c-1; j>=pos; j--){
				int now2 = D[j].second+stRtoL.countRtoL(D[j].second)-stLtoR.countLtoR(D[j].second);
				ans += r-now2;
				stLtoR.update(D[j].second);
				r--;
				//cout << now2 << " " <<  ans << endl;
			}
		}
		//cout << ans << endl;
	}
	cout << ans << endl;

	return 0;
}

Compilation message

growing.cpp: In member function 'void SegmentTree::print()':
growing.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<node.size(); i++){
                ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2428 KB Output is correct
2 Correct 75 ms 4784 KB Output is correct
3 Correct 158 ms 7936 KB Output is correct
4 Correct 192 ms 9064 KB Output is correct
5 Correct 102 ms 9236 KB Output is correct
6 Correct 54 ms 4728 KB Output is correct
7 Correct 327 ms 13700 KB Output is correct
8 Correct 190 ms 15840 KB Output is correct
9 Correct 359 ms 16012 KB Output is correct
10 Correct 227 ms 15968 KB Output is correct