QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85797#4823. No!ScintillaRE 5ms15796kbC++142.2kb2023-03-08 15:39:302023-03-08 15:39:33

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:39:33]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:15796kb
  • [2023-03-08 15:39:30]
  • 提交

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;
    if (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: 100
Accepted
time: 2ms
memory: 15796kb

input:

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

output:

3/1
3/2
3/2
1/0
3/2

result:

ok 5 lines

Test #2:

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

input:

5 6
10 6
3 7
6 15
7 6
8 15
5
3
9
7
7
9

output:

3/1
3/1
6/1
3/1
3/1
6/1

result:

ok 6 lines

Test #3:

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

input:

5 6
7 2020
1 8
10 1
8 1975
6 10
2
9
3
4
9
5

output:

1/2
1/1
1/2
1/2
1/1
1/2

result:

ok 6 lines

Test #4:

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

input:

1 1
8 9
8

output:

1/0

result:

ok single line: '1/0'

Test #5:

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

input:

1 1
3 1
6

output:

1/0

result:

ok single line: '1/0'

Test #6:

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

input:

7 9
44 51
91 191
1 6
67 3
94 191
87 58
59 10
54
80
37
63
27
9
28
85
44

output:

191/37
191/11
191/47
191/28
3/1
191/82
51/16
191/6
191/47

result:

ok 9 lines

Test #7:

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

input:

7 9
56 11172
5 9
79 2674
31 3263
38 4607
36 5
82 1814
41
24
52
22
30
92
74
48
67

output:

2674/23
2674/23
2674/23
2674/23
2674/23
1/0
2674/5
2674/23
1337/6

result:

ok 9 lines

Test #8:

score: -100
Runtime Error

input:

10 10
1465292 914022939
2258868 101102159
265616 463724951
192430 946841485
2630886 977373286
2016747 443115809
3552227 644307708
3999290 745677354
424627 330625475
2046399 18914556
2263191
3680274
839068
1905778
257097
2496977
3578950
1400222
3781916
2618199

output:


result: