QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85796 | #4823. No! | Scintilla | WA | 5ms | 14604kb | C++14 | 2.2kb | 2023-03-08 15:38:46 | 2023-03-08 15:38:49 |
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;
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'