Submission #778313

#	Time	Username	Problem	Language	Result	Execution time	Memory
778313		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	258 ms	26160 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
const int N = 2e5+37;
priority_queue<array<int, 2>> adj[N];
array<int, 2> st[N*4];

void update(int v, int l, int r,int pos, array<int, 2> val){
	if(l==r) st[v] = val;
	else if(l<r){
		int mid = (r+l)/2;
		if(pos <= mid) update(v*2, l, mid, pos, val);
		else update(v*2+1, mid+1, r, pos, val);

		st[v] = max(st[v*2], st[v*2+1]);
	}
}

array<int, 2> get(int v, int l, int r,int tl,int tr){
	if(l>r || tr < l || r < tl) return {-1, -1};
	else if(l>=tl && r<= tr) return st[v];
	else{
		int mid = (r+l)/2;
		return max(get(v*2, l, mid, tl, tr), 
			       get(v*2+1, mid+1, r, tl, tr));

	}
}

void f(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {

	int n=s.size();
	vector<array<int, 2>> q(n);
	for(int i=0; i<n*4+37; i++){
		st[i]={-1, -1};
	}
	for(int i=0; i<n; i++){
		q[i]={s[i], t[i]};
	}

	sort(s.begin(), s.end());
	sort(q.begin(), q.end());
	vector<int> e(n), pe(n);

	for(int i=0; i<n; i++){
		auto k=upper_bound(s.begin(), s.end(), q[i][0])-s.begin();
		auto f=upper_bound(s.begin(), s.end(), q[i][1])-s.begin();
		adj[k].push({(int)f, i});
		e[i] = f;
		pe[i] = k;

	}

	for(int i=0; i<n; i++){
		if(adj[i].size()){
			update(1, 0, n, i, {adj[i].top()});
		}
	}

	vector<int> vis(n+1);
	queue<int> qu;

	qu.push(0);

	while(qu.size()){
		int f=qu.front(); qu.pop();

		if(f==-1) break;
		vis[f] =1;
		int c=adj[pe[f]].size();
		while(adj[pe[f]].size()&&vis[adj[pe[f]].top()[1]]){
			adj[pe[f]].pop();
		}

		if(adj[pe[f]].size()){
			update(1, 0, n, pe[f], adj[pe[f]].top());
		}
		else if(c){
			update(1, 0, n, pe[f], {-1, -1});
		}

		auto k=get(1, 0, n, 0, e[f])[1];
		qu.push(k);
	}
	q.clear();

	for(int i=0; i<n; i++){
		adj[i]=priority_queue<array<int, 2>>();
	}

	for(int i=0; i<n*4+37; i++){
		st[i]={-1, -1};
	}

	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		adj[e[i]].push({(int)pe[i], i});


	}

	qu.push(0);

	for(int i=0; i<n; i++){
		if(adj[i].size()){
			update(1, 0, n, i, {adj[i].top()});
		}
	}

	while(qu.size()){
		int f=qu.front(); qu.pop();

		if(f==-1) break;
		vis[f] =1;
		int c=adj[e[f]].size();
		while(adj[e[f]].size()&&vis[adj[e[f]].top()[1]]){
			adj[e[f]].pop();
		}

		if(adj[e[f]].size()){
			update(1, 0, n, e[f], adj[e[f]].top());
		}
		else if(c){
			update(1, 0, n, e[f], {-1, -1});
		}

		auto k=get(1, 0, n, 0, pe[f])[1];
		qu.push(k);
	}
	for(int i=0; i<n; i++) if(!vis[i]) return 1;
	return 0;

}

Compilation message (stderr)

railroad.cpp: In function 'void f()':
railroad.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railroad.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36