제출 #778402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778402		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	446 ms	62052 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
const int N = 4e5+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] = min(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 {N, N};
	else if(l>=tl && r<= tr) return st[v];
	else{
		int mid = (r+l)/2;
		return min(get(v*2, l, mid, tl, tr), 
			       get(v*2+1, mid+1, r, tl, tr));

	}
}

void update2(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) update2(v*2, l, mid, pos, val);
		else update2(v*2+1, mid+1, r, pos, val);

		st[v] = max(st[v*2], st[v*2+1]);
	}
}
array<int, 2> get2(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(get2(v*2, l, mid, tl, tr), 
			       get2(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) {


	map<int, int> mp;

	vector<int> j;

	for(auto i: s) j.push_back(i);
	for(auto i: t) j.push_back(i);

		sort(j.begin(), j.end());
	int cur=0;
	for(auto i:j){
		if(mp.count(i)) continue;
		mp[i]=cur; cur++;
	}

	for(auto &i: s) i=mp[i];
	for(auto &i: t) i=mp[i];

	int n=s.size();


	vector<array<int, 2>> q(n);
	for(int i=0; i<n*4*2+37; i++){
		st[i]={N, N};
	}
	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++){
		e[i] = q[i][1];
		pe[i] = q[i][0];
		adj[pe[i]].push({(int)-e[i], i});
	

	}

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

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

	qu.push(0);

	while(qu.size()){
		int f=qu.front(); qu.pop();
		//cout<<f<<"\n";
		if(f==N) 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, 2*n, pe[f], {-adj[pe[f]].top()[0], adj[pe[f]].top()[1]});
		}
		else if(c){
			update(1, 0, 2*n, pe[f], {N, N});
		}

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

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

	for(int i=0; i<n*4*2+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()){
			update2(1, 0, n*2, 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()){
			update2(1, 0, n*2, e[f], adj[e[f]].top());
		}
		else if(c){
			update2(1, 0, n*2, e[f], {-1, -1});
		}

		auto k=get2(1, 0, n*2, 0, pe[f])[1];
		qu.push(k);
	}

	for(int i=0; i<n; i++) if(vis[i]==0) return 1;
		return 0;
}
/*
int main() {

	f();
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}*/

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

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

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