QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67562#949. Roadsalpha1022100 ✓128ms9788kbC++231.6kb2022-12-10 17:27:042022-12-10 17:27:05

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 17:27:05]
  • Judged
  • Verdict: 100
  • Time: 128ms
  • Memory: 9788kb
  • [2022-12-10 17:27:04]
  • Submitted

answer

#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int N = 1e5;
const int inf = 0x3f3f3f3f;

int n;
struct Point {
  int x, y;
  inline Point(int x = 0, int y = 0): x(x), y(y) {}
  inline bool operator<(const Point &o) const {
    return x != o.x ? x < o.x : y < o.y;
  }
};
struct Segment {
  Point s, t;
  inline Segment(Point s = Point(), Point t = Point()): s(s), t(t) {}
  inline double get(int x) const {
    if (s.x == t.x)
      return s.y;
    return s.y + (double)(t.y - s.y) / (t.x - s.x) * (x - s.x);
  }
  inline bool operator<(const Segment &o) const {
    int x = max(s.x, o.s.x);
    return get(x) < o.get(x);
  }
} a[N + 5];
vector<pair<Point, int>> p;
map<Segment, Point> vis;

int main() {
  //freopen("network.in", "r", stdin), freopen("network.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d%d", &a[i].s.x, &a[i].s.y, &a[i].t.x, &a[i].t.y);
    if (a[i].t < a[i].s)
      swap(a[i].s, a[i].t);
    p.emplace_back(a[i].s, i), p.emplace_back(a[i].t, i);
  }
  sort(p.begin(), p.end());
  vis.emplace(Segment(Point(-inf, -inf), Point(-inf, inf)), Point());
  for (int i = 0; i < p.size(); ++i) {
    Point x;
    int id;
    tie(x, id) = p[i];
    if (x < a[id].t) {
      auto it = --vis.emplace(a[id], x).first;
      if (i)
        printf("%d %d %d %d\n", it->second.x, it->second.y, x.x, x.y);
      it->second = x;
    } else {
      auto it = vis.find(a[id]);
      prev(it)->second = x;
      vis.erase(it);
    }
  }
}

Details

Subtask #1:

score: 0
Accepted

Test #1:

score: 0
Accepted
time: 4ms
memory: 4736kb

Test #2:

score: 0
Accepted
time: 18ms
memory: 5940kb

Subtask #2:

score: 15
Accepted

Test #3:

score: 15
Accepted
time: 0ms
memory: 4600kb

Test #4:

score: 0
Accepted
time: 3ms
memory: 4744kb

Test #5:

score: 0
Accepted
time: 4ms
memory: 4776kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 4716kb

Test #7:

score: 0
Accepted
time: 27ms
memory: 5116kb

Subtask #3:

score: 15
Accepted

Test #8:

score: 15
Accepted
time: 4ms
memory: 4576kb

Test #9:

score: 0
Accepted
time: 3ms
memory: 4752kb

Test #10:

score: 0
Accepted
time: 4ms
memory: 4696kb

Test #11:

score: 0
Accepted
time: 15ms
memory: 4700kb

Test #12:

score: 0
Accepted
time: 128ms
memory: 7288kb

Subtask #4:

score: 15
Accepted

Test #13:

score: 15
Accepted
time: 1ms
memory: 4600kb

Test #14:

score: 0
Accepted
time: 3ms
memory: 4692kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 4776kb

Test #16:

score: 0
Accepted
time: 11ms
memory: 4772kb

Test #17:

score: 0
Accepted
time: 51ms
memory: 5840kb

Subtask #5:

score: 15
Accepted

Test #18:

score: 15
Accepted
time: 2ms
memory: 4664kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 4644kb

Test #20:

score: 0
Accepted
time: 3ms
memory: 4648kb

Test #21:

score: 0
Accepted
time: 3ms
memory: 4668kb

Test #22:

score: 0
Accepted
time: 1ms
memory: 4656kb

Test #23:

score: 0
Accepted
time: 3ms
memory: 4664kb

Test #24:

score: 0
Accepted
time: 4ms
memory: 4700kb

Test #25:

score: 0
Accepted
time: 3ms
memory: 4584kb

Test #26:

score: 0
Accepted
time: 7ms
memory: 4936kb

Test #27:

score: 0
Accepted
time: 2ms
memory: 4720kb

Test #28:

score: 0
Accepted
time: 5ms
memory: 4808kb

Subtask #6:

score: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #29:

score: 40
Accepted
time: 64ms
memory: 7808kb

Test #30:

score: 0
Accepted
time: 76ms
memory: 8696kb

Test #31:

score: 0
Accepted
time: 2ms
memory: 4692kb

Test #32:

score: 0
Accepted
time: 69ms
memory: 5736kb

Test #33:

score: 0
Accepted
time: 79ms
memory: 5808kb

Test #34:

score: 0
Accepted
time: 103ms
memory: 7352kb

Test #35:

score: 0
Accepted
time: 115ms
memory: 7280kb

Test #36:

score: 0
Accepted
time: 108ms
memory: 9788kb

Extra Test:

score: 0
Extra Test Passed