QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85797 | #4823. No! | Scintilla | RE | 5ms | 15796kb | C++14 | 2.2kb | 2023-03-08 15:39:30 | 2023-03-08 15:39:33 |
Judging History
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