oj.uz

Submission #57456

# Submission time Handle Problem Language Result Execution time Memory
57456 2018-07-15T05:43:01 Z leejseo 공장 (KOI13_factory) C++17
0 / 20
 1000 ms 18416 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int X[1000001], N;
vector<int> L;
vector<int> temp;


void input(){
	scanf("%d", &N);
	int val;
	for (int i=0; i<N; i++){
		scanf("%d", &val);
		X[val] = i;
	}
	for (int i=0; i<N; i++){
		scanf("%d", &val);
		L.push_back(X[val]);
	}
	L.push_back((int) 1e9);
}

lld merge_sort(int fr, int ed){
	if (ed <= fr+3){
		lld ans = 0;
		for (int i=fr; i<=ed; i++){
			for (int j=fr; j<i; j++){
				if (L[j] > L[i]) ans++;
			}
		}
		for (int i=fr; i<=ed; i++){
			for (int j=fr; j<i; j++){
				if (L[j] > L[i]){
					L[i] ^= L[j];
					L[j] ^= L[i];
					L[i] ^= L[j];
				}
			}
		}
		//printf("%d %d %lld\n", fr, ed, ans);
		return ans;
	}
	int mid = (fr + ed) >>1;
	lld val = merge_sort(fr, mid) + merge_sort(mid+1, ed);
	int lo = 0, hi = mid+1;
	while (lo < mid+1 || hi < ed+1){
		//printf("%d %d\n", lo, hi);
		if (hi > ed || (lo < mid+1 && L[lo] < L[hi])){
			temp.push_back(L[lo++]);
			continue;
		}
		else{
			temp.push_back(L[hi++]);
			val += (lld) mid - lo + 1;
			continue;
		}
	}
	for (int i=0; i<ed-fr+1; i++){
		L[i+lo] = temp[i];
	}
	temp.clear();
	//printf("%d %d %lld\n", fr, ed, val);
	return val;
}

int main(void){
	input();
	//for (int i=0; i<N; i++){
	//	printf("%d ", L[i]);
	//}
	//printf("\n");
	lld ans = merge_sort(0, N-1);
	printf("%lld\n", ans);
}

Compilation message

factory.cpp: In function 'void input()':
factory.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
factory.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val);
   ~~~~~^~~~~~~~~~~~
factory.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 2.2

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 608 KB Output is correct
3 Runtime error 8 ms 1436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 3.4

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 5968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.8

# Verdict Execution time Memory Grader output
1 Runtime error 396 ms 10008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 11692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.8

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 18416 KB Time limit exceeded
2 Halted 0 ms 0 KB -