oj.uz

답안 #415472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415472 2021-06-01T06:46:33 Z 장태환(#7545) Road Construction (JOI21_road_construction) C++17
5 / 100
 3174 ms 756712 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#define int long long
using namespace std;
struct node
{
	pair<int,int> val;
	int l, r;
	node()
	{
		val = { 1LL<<50,0 };
		l = r = -1;
	}
};
int treeN;
struct pst
{
	vector<node>ps;
	int root[300100];
	int rootc = 0;
	void init()
	{
		ps.clear();
		node be;
		ps.push_back(be);
		root[0] = 0;
		rootc = 1;
	}
	void upd(int po, int ind, int s, int e,pair<int,int>v)
	{
		if (s == e)
		{
			ps[ind].val = v;
			return;
		}
		int m = (s + e) >> 1;
		if (po <= m)
		{
			node x;
			if (ps[ind].l >= 0)
				x = ps[ps[ind].l];
			ps.push_back(x);
			ps[ind].l = ps.size() - 1;
			upd(po, ps.size() - 1, s, m, v);
		}
		else
		{
			node x;
			if(ps[ind].r>=0)
				x=ps[ps[ind].r];
			ps.push_back(x);
			ps[ind].r = ps.size() - 1;
			upd(po, ps.size() - 1, m+1, e, v);
		}
		ps[ind].val = { 1LL<<50,0 };
		if (ps[ind].l>=0)
		{
			ps[ind].val = min(ps[ind].val, ps[ps[ind].l].val);
		}
		if (ps[ind].r >= 0)
		{
			ps[ind].val = min(ps[ind].val, ps[ps[ind].r].val);
		}
	}
	void update(int n,pair<int,int> k,int bef)
	{
		node be;
		be = ps[root[bef]];
		ps.push_back(be);
		root[rootc++] = ps.size()-1;
		upd(n, root[rootc - 1], 0, treeN - 1, k);
	}
	pair<int,int> qur(int qs,int qe, int ind, int s, int e)
	{
		if (qs > e || s > qe||ind==-1)
		{
			return { 1LL<<50,0 };
		}
		if (qs <= s && e <= qe)
			return ps[ind].val;
		int m = (s + e) >> 1;
		return min(qur(qs,qe,ps[ind].l, s, m),qur(qs, qe, ps[ind].r, m+1,e));
	}
	pair<int, int> query(int ind, int s, int e)
	{
		return qur(s, e, root[ind], 0, treeN - 1);
	}
}u,d;
int ru[300100];
int rd[300100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, K;
	cin >> N >> K;
	int i;
	vector<pair<int, int>>x;
	vector<pair<int,int>>y;
	for (i = 0; i < N; i++)
	{
		ru[i] = rd[i] = i;
		int a, b;
		cin >> a >> b;
		x.push_back({ a,b });
	}
	sort(x.begin(), x.end());
	for (i = 0; i < N; i++)
	{
		y.push_back({ x[i].second,i });
	}
	sort(y.begin(), y.end());
	y.erase(unique(y.begin(), y.end()), y.end());
	for (treeN = 1; treeN < y.size(); treeN *=2);
	u.init();
	d.init();
	for (i = 0; i < N; i++)
	{
		u.update(lower_bound(y.begin(), y.end(), make_pair( x[i].second,i )) - y.begin(), { -x[i].first + x[i].second,i }, i);
		d.update(lower_bound(y.begin(), y.end(), make_pair(x[i].second, i)) - y.begin(), { -x[i].first - x[i].second,i }, i);
	}
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	for (i = 0; i < N; i++)
	{
		auto f = u.query(ru[i] , lower_bound(y.begin(), y.end(), make_pair(x[i].second, i)) - y.begin(), treeN - 1);
		auto s = d.query(rd[i], 0, lower_bound(y.begin(), y.end(), make_pair(x[i].second, i)) - y.begin());
		f.first += x[i].first - x[i].second;
		s.first += x[i].first + x[i].second;
		if (f.first < s.first)
		{
			pq.push({ f.first,i });
			u.update(lower_bound(y.begin(), y.end(), make_pair(x[f.second].second, f.second)) - y.begin(), { 1LL << 50,f.second }, ru[i]);
			ru[i] = u.rootc - 1;
		}
		else
		{
			swap(f, s);
			pq.push({ f.first,i });
			d.update(lower_bound(y.begin(), y.end(), make_pair(x[f.second].second, f.second)) - y.begin(), { 1LL << 50,f.second }, rd[i]);
			rd[i] = d.rootc - 1;
		}
	}
	for (i = 0; i < K; i++)
	{
		auto a = pq.top();
		pq.pop();
		cout << a.first << '\n';
		auto f = u.query(ru[a.second], lower_bound(y.begin(), y.end(), make_pair(x[a.second].second, a.second)) - y.begin(), treeN - 1);
		auto s = d.query(rd[a.second], 0,lower_bound(y.begin(), y.end(), make_pair(x[a.second].second, a.second)) - y.begin());
		f.first += x[a.second].first - x[a.second].second;
		s.first += x[a.second].first + x[a.second].second;
		if (f.first < s.first)
		{
			pq.push({ f.first,a.second });
			u.update(lower_bound(y.begin(), y.end(), make_pair(x[f.second].second, f.second)) - y.begin(), { 1LL << 50,f.second }, ru[a.second]);
			ru[a.second] = u.rootc - 1;
		}
		else
		{
			swap(f, s);
			pq.push({ f.first,a.second });
			d.update(lower_bound(y.begin(), y.end(), make_pair(x[f.second].second, f.second)) - y.begin(), { 1LL << 50,f.second }, rd[a.second]);
			rd[a.second] = d.rootc - 1;
		}
	}
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:117:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for (treeN = 1; treeN < y.size(); treeN *=2);
      |                  ~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 102656 KB Output is correct
2 Correct 753 ms 102560 KB Output is correct
3 Correct 608 ms 103252 KB Output is correct
4 Correct 602 ms 127980 KB Output is correct
5 Correct 584 ms 102336 KB Output is correct
6 Correct 7 ms 3132 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1426 ms 692584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2537 ms 756712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2537 ms 756712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 102656 KB Output is correct
2 Correct 753 ms 102560 KB Output is correct
3 Correct 608 ms 103252 KB Output is correct
4 Correct 602 ms 127980 KB Output is correct
5 Correct 584 ms 102336 KB Output is correct
6 Correct 7 ms 3132 KB Output is correct
7 Correct 3174 ms 409652 KB Output is correct
8 Correct 3129 ms 409768 KB Output is correct
9 Correct 529 ms 143536 KB Output is correct
10 Correct 1651 ms 409796 KB Output is correct
11 Correct 2179 ms 409880 KB Output is correct
12 Runtime error 1285 ms 523636 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 102656 KB Output is correct
2 Correct 753 ms 102560 KB Output is correct
3 Correct 608 ms 103252 KB Output is correct
4 Correct 602 ms 127980 KB Output is correct
5 Correct 584 ms 102336 KB Output is correct
6 Correct 7 ms 3132 KB Output is correct
7 Runtime error 1426 ms 692584 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -