Submission #778348

#	Time	Username	Problem	Language	Result	Execution time	Memory
778348		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	2045 ms	26108 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] = 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) 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> 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(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]={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++){
		auto k=lower_bound(s.begin(), s.end(), q[i][0])-s.begin();
		auto f=lower_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()[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, n, pe[f], {-adj[pe[f]].top()[0], adj[pe[f]].top()[1]});
		}
		else if(c){
			update(1, 0, n, pe[f], {N, N});
		}

		auto k=get(1, 0, 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+37; i++){
		st[i]={-1, -1};
	}

	for(int i=0; i<n; i++){
		if(vis[i]) continue;

		int k=upper_bound(s.begin(), s.end(), q[i][0])-s.begin();
		if(s[k-1]=q[i][0]) k--;
		pe[i]=k;
		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, 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, e[f], adj[e[f]].top());
		}
		else if(c){
			update2(1, 0, n, e[f], {-1, -1});
		}

		auto k=get2(1, 0, n, 0, pe[f])[1];
		qu.push(k);
	}
	for(int i=0; i<n; i++) if(!vis[i]) 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;
}
*/

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:126:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  126 |   if(s[k-1]=q[i][0]) k--;
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