Submission #637122

#	Time	Username	Problem	Language	Result	Execution time	Memory
637122		ggoh	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	138 ms	6704 KiB

railroad

//after read editorial :cry:
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

int deg[400004];
lint plan_roller_coaster(vector<int> s, vector<int> t) {

    int n = sz(s);
    lint ans=0;
    vector<int>X;
    for(int i=0;i<n;i++)X.push_back(s[i]);
    for(int i=0;i<n;i++)X.push_back(t[i]);
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    int m=sz(X);
    for(int i=0;i<n;i++)
    {
      deg[lower_bound(X.begin(),X.end(),s[i])-X.begin()]++;
      deg[lower_bound(X.begin(),X.end(),t[i])-X.begin()]--;
    }
    deg[0]--;
    deg[m-1]++;
    int cha=0;
    int ch=0;
    for(int i=0;i<m;i++)
    {
      deg[i]-=cha;
      cha=0;
      if(deg[i]<0)
      { 
        cha=-deg[i];
      }
      else if(deg[i]>0)
      {
        ch=1;break;
      }
    }
    if(cha)ch=1;
    return ch;
}

Compilation message (stderr)

railroad.cpp: In function 'lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:13:10: warning: unused variable 'ans' [-Wunused-variable]
   13 |     lint ans=0;
      |          ^~~

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