oj.uz

답안 #373314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373314 2021-03-04T06:20:37 Z Jasiekstrz Roller Coaster Railroad (IOI16_railroad) C++17
30 / 100
 681 ms 81388 KB 
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
struct Road
{
	int s,t;
	inline bool operator<(const Road &oth)
	{
		if(t==oth.t)
			return s<oth.s;
		return t<oth.t;
	}
};
struct Small
{
	int t,id;
	inline bool operator<(const Small &oth) const
	{
		if(t==oth.t)
			return id<oth.id;
		return t<oth.t;
	}
};
struct Big
{
	int s,id;
	inline bool operator<(const Big &oth) const
	{
		if(s==oth.s)
			return id<oth.id;
		return s<oth.s;
	}
};
const int N=2e5;
const int INF=1e9+7;
Road tab[N+10];
set<Small> sm;
set<Big> bg;
set<int> occ[N+10];
int id[N+10];
int wh[N+10];
long long plan_roller_coaster(vector<int> s,vector<int> t)
{
	int n=s.size();
	for(int i=0;i<n;i++)
		tab[i]={s[i],t[i]};
	sort(tab,tab+n);
	sm.insert({0,n});
	bg.insert({INF,n});
	for(int i=0;i<n;i++)
	{
		while(!bg.empty() && (bg.begin()->s)<tab[i].t)
		{
			auto x=*bg.begin();
			bg.erase(x);
			auto it=prev(sm.end());
			if(occ[it->id].find(x.id)!=occ[it->id].end())
				it--;
			auto tmp=*it;
			sm.erase(it);
			if(occ[tmp.id].size()>occ[id[x.id]].size())
			{
				int x_id=id[x.id];
				for(auto v:occ[x_id])
				{
					occ[tmp.id].insert(v);
					id[v]=tmp.id;
				}
				sm.erase({wh[x_id],x_id});
				id[x.id]=tmp.id;
				wh[tmp.id]=wh[x_id];
				sm.insert({wh[id[x.id]],id[x.id]});
			}
			else
			{
				for(auto v:occ[tmp.id])
				{
					occ[id[x.id]].insert(v);
					id[v]=id[x.id];
				}
			}
		}
		auto it=sm.upper_bound({tab[i].s,INF});
		if(it==sm.begin() || sm.empty())
		{
			return 1;
		}
		if(tab[i].s>tab[i].t)
		{
			occ[i].insert(i);
			id[i]=i;
			wh[i]=tab[i].t;
			sm.insert({tab[i].t,i});
			bg.insert({tab[i].s,i});
		}
		else
		{
			auto tmp=*prev(it);
			sm.erase(prev(it));
			occ[tmp.id].insert(i);
			id[i]=tmp.id;
			wh[tmp.id]=tab[i].t;
			sm.insert({tab[i].t,tmp.id});
		}
	}
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9708 KB n = 2
2 Correct 6 ms 9708 KB n = 2
3 Correct 6 ms 9708 KB n = 2
4 Correct 6 ms 9708 KB n = 2
5 Correct 6 ms 9708 KB n = 2
6 Incorrect 6 ms 9708 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9708 KB n = 2
2 Correct 6 ms 9708 KB n = 2
3 Correct 6 ms 9708 KB n = 2
4 Correct 6 ms 9708 KB n = 2
5 Correct 6 ms 9708 KB n = 2
6 Incorrect 6 ms 9708 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 664 ms 59896 KB n = 199999
2 Correct 355 ms 35436 KB n = 199991
3 Correct 86 ms 18284 KB n = 199993
4 Correct 512 ms 61804 KB n = 152076
5 Correct 275 ms 37484 KB n = 93249
6 Correct 288 ms 60140 KB n = 199910
7 Correct 229 ms 49516 KB n = 199999
8 Correct 234 ms 48748 KB n = 199997
9 Correct 490 ms 67436 KB n = 171294
10 Correct 498 ms 62060 KB n = 140872
11 Correct 79 ms 17260 KB n = 199886
12 Correct 97 ms 17724 KB n = 199996
13 Correct 96 ms 17260 KB n = 200000
14 Correct 81 ms 17516 KB n = 199998
15 Correct 81 ms 17388 KB n = 200000
16 Correct 86 ms 17772 KB n = 199998
17 Correct 105 ms 18284 KB n = 200000
18 Correct 144 ms 32104 KB n = 190000
19 Correct 207 ms 43932 KB n = 177777
20 Correct 218 ms 41580 KB n = 100000
21 Correct 495 ms 77548 KB n = 200000
22 Correct 466 ms 54508 KB n = 200000
23 Correct 681 ms 81388 KB n = 200000

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9708 KB n = 2
2 Correct 6 ms 9708 KB n = 2
3 Correct 6 ms 9708 KB n = 2
4 Correct 6 ms 9708 KB n = 2
5 Correct 6 ms 9708 KB n = 2
6 Incorrect 6 ms 9708 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -