oj.uz

Submission #498602

# Submission time Handle Problem Language Result Execution time Memory
498602 2021-12-25T17:15:32 Z codebuster_10 Roads (CEOI20_roads) C++17
100 / 100
 264 ms 20016 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t //be careful about this 

#define pr pair
#define ar array
#define f first
#define s second
#define vt vector
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x;}
template<class H, class... T> void rd(H& h, T&... t) { rd(h); rd(t...);}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a);}

template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;}

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
#define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)


void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); 
	cout.precision(20);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}


/*/--------------------------------------------------look below-----------------------------------------------------------------------------------/*/



























struct point{
	int x,y,id;
};

struct line{
	point s,e;
};

bool operator<(const point& a,const point& b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

int curr_x;

bool operator<(const line& a,const line& b){
	double yA, yB;
  if(a.s.x == a.e.x) yA = a.s.y;
  else{
    double m = double(a.e.y - a.s.y) / (a.e.x - a.s.x);
    double c = a.s.y - m * a.s.x;
    yA = m * curr_x + c;
  }
  if(b.s.x == b.e.x) yB = b.s.y;
  else {
    double m = double(b.e.y - b.s.y) / (b.e.x - b.s.x);
    double c = b.s.y - m * b.s.x;
    yB = m * curr_x + c;
  }
  return yA < yB;
}



bool operator==(const line& a,const line& b){
    return a.s.id == b.s.id;
}

signed main(){
  setIO();
  int n;
  rd(n);
  vt<line> s(n);
  vt<point> Rmost(n+1);
  vt<point> events;
  for(int i = 0; i < n; ++i){
  	rd(s[i].s.x,s[i].s.y,s[i].e.x,s[i].e.y);
  	if(s[i].e < s[i].s)
  		swap(s[i].s,s[i].e);
  	s[i].s.id=s[i].e.id=i;
  	events.pb(s[i].s);
  	events.pb(s[i].e);
  }
  sort(all(events));
  set<line> active;
  point ninf = {INT_MIN, INT_MAX, n}, inf = {INT_MAX, INT_MAX, n};
  active.insert({ninf, inf});
  Rmost[n] = {0, 0, -1};

  for(auto i : events){
  	curr_x = i.x;
  	if(active.find(s[i.id]) != active.end()){
  		active.erase(s[i.id]);
  		auto nxt = active.lower_bound(s[i.id]);
      Rmost[nxt->s.id] = i;
  	}else{
  		auto nxt = active.lower_bound(s[i.id]);
  		if(Rmost[nxt->s.id].id != -1){
        cout << Rmost[nxt->s.id].x << " " << Rmost[nxt->s.id].y << " " << i.x << " " << i.y << '\n';
      }
      Rmost[i.id] = Rmost[nxt->s.id] = i;
      active.insert(s[i.id]);
  	}
  }
  
  return 0;
}







// tips to avoid bugs.

/*
	* be careful of whats happening you dont want a continue statement to miss imp line of code.
	* be careful when to update what since it might be needed in next segment of code.
	* dont get stuck on one idea.
  * dont use too much space bar so that code is written quickly as possible.
*/

Compilation message

roads.cpp: In function 'void setIO(std::string)':
roads.cpp:81:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roads.cpp:82:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 69 ms 6832 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 11 ms 1932 KB Output is correct
5 Correct 23 ms 3424 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 11 ms 1864 KB Output is correct
5 Correct 22 ms 3424 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 13 ms 1868 KB Output is correct
10 Correct 195 ms 15292 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 10 ms 1864 KB Output is correct
5 Correct 22 ms 3360 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 10 ms 1864 KB Output is correct
10 Correct 53 ms 7784 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 11 ms 2204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 14 ms 2144 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 456 KB Output is correct
13 Correct 11 ms 2120 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 312 KB Output is correct
20 Correct 2 ms 436 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 7 ms 1040 KB Output is correct
23 Correct 6 ms 1056 KB Output is correct
24 Correct 14 ms 1600 KB Output is correct
25 Correct 1 ms 312 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 77 ms 6948 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 11 ms 2208 KB Output is correct
7 Correct 24 ms 3904 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 452 KB Output is correct
11 Correct 12 ms 2200 KB Output is correct
12 Correct 197 ms 18028 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 11 ms 2100 KB Output is correct
17 Correct 62 ms 9248 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 416 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 7 ms 1024 KB Output is correct
27 Correct 6 ms 1040 KB Output is correct
28 Correct 14 ms 1660 KB Output is correct
29 Correct 139 ms 12080 KB Output is correct
30 Correct 167 ms 17212 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 128 ms 12092 KB Output is correct
33 Correct 126 ms 12080 KB Output is correct
34 Correct 198 ms 15944 KB Output is correct
35 Correct 191 ms 16544 KB Output is correct
36 Correct 264 ms 20016 KB Output is correct