제출 #202559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202559		arnold518	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	10 ms	6648 KiB

bridge

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

int M, K, N;
pii A[MAXN+10];
ll ans;

int S;
vector<int> comp;

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin(); }

pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }

struct SEG
{
	int tree[MAXN*4+10], sz;
	pll tree2[MAXN+10];

	SEG()
	{
		int i, j;
		for(i=0; i<MAXN*4+10; i++) tree[i]=0;
		for(i=0; i<MAXN+10; i++) tree2[i]=pll(0, 0);
		sz=0;
	}
	void update(int node, int tl, int tr, int pos)
	{
		if(tl==tr) { tree[node]++; return; }
		int mid=tl+tr>>1;
		if(pos<=mid) update(node*2, tl, mid, pos);
		else update(node*2+1, mid+1, tr, pos);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
	void update2(int i, pll k) { for(; i<=S; i+=(i&-i)) tree2[i]=tree2[i]+k; }
	void update(int l, int r)
	{
		update(1, 1, S, getcomp(l));
		update(1, 1, S, getcomp(r));
		update2(1, pll(-2, 2*l));
		update2(getcomp(l), pll(2, -2*l));
		update2(getcomp(r), pll(2, -2*r));
		//printf("!%d %d\n", getcomp(l), getcomp(r));
		sz++;
	}
	int query(int node, int tl, int tr, int k)
	{
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(k<=tree[node*2]) return query(node*2, tl, mid, k);
		else return query(node*2+1, mid+1, tr, k-tree[node*2]);
	}
	pll query2(int i) { pll ret(0, 0); for(; i>0; i-=(i&-i)) ret=ret+tree2[i]; return ret; }
	ll query()
	{
		int t=query(1, 1, S, sz);
		pll tt=query2(t);
		//printf("%d / %lld %lld\n", t, tt.first, tt.second);
		return tt.first*comp[t]+tt.second;
	}
}seg;

ll P[MAXN+10], Q[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d", &K, &M);
	for(i=1; i<=M; i++)
	{
		char a, c;
		int b, d;
		scanf(" %c%d %c%d", &a, &b, &c, &d);
		assert(a=='A' || a=='B');
		assert(c=='A' || c=='B');
		if(b>d) swap(b, d);
		ans+=d-b;
		if(a!=c) A[++N]=pii(b, d), ans++;
	}
	sort(A+1, A+N+1, [&](const pii &p, const pii &q) { return p.first+q.first<p.second+q.second; });

	for(i=1; i<=N; i++)
	{
		comp.push_back(A[i].first);
		comp.push_back(A[i].second);
	}
	comp.push_back(-1);

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	S=comp.size()-1;

	ll q=INF;
	for(j=1; j<=S; j++)
	{
		ll p=0;
		int pos=comp[j];
		for(i=1; i<=N; i++)
		{
			if(pos<A[i].first) p+=(ll)(A[i].first-pos)*2;
			if(A[i].second<pos) p+=(ll)(pos-A[i].second)*2;
		}
		q=min(q, p);
	}
	printf("%lld\n", ans+q);
/*
	seg=SEG();
	for(i=1; i<=N; i++)
	{
		seg.update(A[i].first, A[i].second);
		P[i]=seg.query();
	}
	seg=SEG();
	for(i=N; i>=1; i--) 
	{
		seg.update(A[i].first, A[i].second);
		Q[i]=seg.query();
	}
	if(K==1) printf("%lld\n", ans+P[N]);
*/
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In constructor 'SEG::SEG()':
bridge.cpp:29:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
bridge.cpp: In member function 'void SEG::update(int, int, int, int)':
bridge.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
bridge.cpp: In member function 'int SEG::query(int, int, int, int)':
bridge.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &M);
  ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37