Submission #82845

#	Time	Username	Problem	Language	Result	Execution time	Memory
82845		leejseo	공장 (KOI13_factory)	C++11	20 / 20	256 ms	62484 KiB

factory

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

typedef struct BIT{
	lld tree[524288];
	const int MAXN = 524288;
	lld sum(int i){
		lld ans = 0;
		while (i > 0){
			ans += tree[i];
			i -= (i & -i);
		}
		return ans;
	}
	void update(int i, lld diff){
		while (i < MAXN){
			tree[i] += diff;
			i += (i & -i);
		}
	}
} BIT;

int N, I[1000001];
vector<int> L;
BIT tree;

void input(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++){
		int temp;
		scanf("%d", &temp);
		I[temp] = i;
	}
	L.push_back(-1);
	for (int i=1; i<=N; i++){
		int temp;
		scanf("%d", &temp);
		L.push_back(I[temp]);
	}
}

lld solve(){
	lld ans = 0;
	for (int i=1; i<=N; i++){
		ans += i - tree.sum(L[i]) - 1;
		tree.update(L[i], 1);
	}
	return ans;
}

int main(void){
	input();
	printf("%lld\n", solve());
}

Compilation message (stderr)

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

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8