QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85796#4823. No!ScintillaWA 5ms14604kbC++142.2kb2023-03-08 15:38:462023-03-08 15:38:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-08 15:38:49]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:14604kb
  • [2023-03-08 15:38:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using pii = pair <int, int>;

const int INF = 0x3f3f3f3f;

const int N = 5e5 + 10;
const int W = 4e6 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

template <typename T> void cmax(T &a, T b) { a < b ? a = b : 1; }
template <typename T> void cmin(T &a, T b) { b < a ? a = b : 1; }

struct frac {
  int p, q;
  frac(int _p = 0, int _q = 1) {
    p = _p, q = _q;
    if (q < 0) p = -p, q = -q;
  }
  friend bool operator < (frac a, frac b) {
    return 1ll * a.p * b.q < 1ll * b.p * a.q;
  }
  void norm() {
    int g = __gcd(p, q);
    p /= g, q /= g;
  }
  void print() {
    printf("%d/%d\n", p, q);
  }
} ;

struct vec {
  int x, y;
  vec(int _x = 0, int _y = 0) {
    x = _x, y = _y;
  }
} ;

frac slope(vec a, vec b) {
  return frac(b.y - a.y, b.x - a.x);
}

int n, q, w, s[N], f[N], top;
vec st[N];
pii qry[N];
frac ans[N];

int main() {
  n = read(), q = read();
  rep(i, 1, n) {
    int h = read();
    cmax(w, h), cmax(s[h], read());
  }
  rep(i, 1, q) {
    qry[i].first = read(), qry[i].second = i;
    cmax(w, qry[i].first);
  }
  sort(qry + 1, qry + q + 1);
  frac res(1, 0);
  for (int i = w, j = q; i; -- i) {
    for (; j && qry[j].first == i; -- j) {
      ans[qry[j].second] = res;
    }
    if (s[i]) {
      vec it(i, s[i]);
      while ((top > 1 && slope(st[top], it) < slope(st[top - 1], st[top])) || (top && st[top].y <= s[i])) -- top;
      st[++ top] = it;
    }
    while (top > 1 && slope(vec(i - 1, 0), st[top]) < slope(vec(i - 1, 0), st[top - 1])) -- top;
    cmin(res, slope(vec(i - 1, 0), st[top]));
  }
  rep(i, 1, q) {
    ans[i].norm();
    ans[i].print();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 14604kb

input:

4 5
3 5
4 3
2 5
6 3
5
2
3
7
2

output:

0/1
0/1
0/1
1/0
0/1

result:

wrong answer 1st lines differ - expected: '3/1', found: '0/1'