Submission #30067

#	Time	Username	Problem	Language	Result	Execution time	Memory
30067		gs14004	무제 (POI11_rot)	C++14	0 / 100	169 ms	8408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
const int MAXN = 200005;

int a[MAXN], n, cnt;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		while(x <= n){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x) ret += tree[x], x -= x & -x;
		return ret;
	}
}bit;

lint solve(int s, int m, int e){
	lint ans = 0;
	if(e - m > m - s){
		for(int j=s; j<m; j++) bit.add(a[j], -1);
		for(int j=s; j<m; j++) ans += bit.query(a[j] - 1);
		for(int j=s; j<m; j++) bit.add(a[j], 1);
	}
	else{
		for(int j=m; j<e; j++) bit.add(a[j], -1);
		for(int j=m; j<e; j++) ans += m - s - bit.query(a[j]);
		for(int j=m; j<e; j++) bit.add(a[j], 1);
	}
	return ans;
}

lint solve(){
	int x;
	scanf("%d",&x);
	lint ans = 0;
	if(x == 0){
		int s = cnt;
		ans += solve();
		int m = cnt;
		ans += solve();
		int e = cnt;
		lint tmp = solve(s, m, e);
		ans += min(tmp, 1ll * (e - m) * (m - s) - tmp);
	}
	else{
		bit.add(x, 1);
		a[cnt++] = x;
	}
	return ans;
}

int main(){
	scanf("%d",&n);
	printf("%lld\n", solve());
}

Compilation message (stderr)

rot.cpp: In function 'lint solve()':
rot.cpp:42:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^
rot.cpp: In function 'int main()':
rot.cpp:61:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10