oj.uz

Submission #82845

# Submission time Handle Problem Language Result Execution time Memory
82845 2018-11-02T06:15:34 Z leejseo 공장 (KOI13_factory) C++11
20 / 20
 256 ms 62484 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1620 KB Output is correct
5 Correct 4 ms 2328 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3424 KB Output is correct
2 Correct 10 ms 4984 KB Output is correct
3 Correct 9 ms 5236 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6012 KB Output is correct
2 Correct 24 ms 6852 KB Output is correct
3 Correct 36 ms 8196 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9772 KB Output is correct
2 Correct 97 ms 12696 KB Output is correct
3 Correct 129 ms 15956 KB Output is correct
4 Correct 174 ms 21004 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 228 ms 27728 KB Output is correct
2 Correct 203 ms 35488 KB Output is correct
3 Correct 200 ms 42284 KB Output is correct
4 Correct 252 ms 49048 KB Output is correct
5 Correct 207 ms 55736 KB Output is correct
6 Correct 256 ms 62484 KB Output is correct