이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifndef FEXT
#include "robots.h"
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
const int N = 5e4 + 5, M = 1e6 + 5;
int n1, n2, m;
pii a[M];
int b[N], c[N];
int f[M], rf[M];
bool ck[M];
auto cmp1 = [](int i, int j){
return a[i].se < a[j].se;
};
priority_queue <int, vi, decltype(cmp1)> pq1(cmp1);
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
n1 = A; n2 = B; m = T;
For(i, 0, n1){
b[i] = X[i];
}
For(i, 0, n2){
c[i] = Y[i];
}
For(i, 0, m){
a[i] = make_pair(W[i], S[i]);
}
sort(a, a + m, [&](const pii &lhs, const pii &rhs){
return lhs.fi < rhs.fi;
});
{
iota(f, f + m, 0);
sort(f, f + m, [&](int i, int j){
return a[i].se < a[j].se;
});
For(i, 0, m){
rf[f[i]] = i;
}
}
sort(b, b + n1);
sort(c, c + n2);
int lo = 1, hi = m + 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(ck, ck + m, 0);
while (!pq1.empty()){
pq1.pop();
}
int j = 0;
For(i, 0, n1){
while (j < m and a[j].fi < b[i]){
pq1.emplace(j);
j++;
}
ForE(turn, 1, mid){
if (pq1.empty()){
break;
}
int j = pq1.top(); pq1.pop();
ck[rf[j]] = 1;
}
}
j = 0;
For(i, 0, n2){
ForE(turn, 1, mid){
while (j < m and ck[j]){
j++;
}
if (j == m or a[f[j]].se >= c[i]){
break;
}
j++;
}
}
while (j < m and ck[j]){
j++;
}
if (j == m){
hi = mid;
}
else{
lo = mid + 1;
}
}
if (lo == m + 1){
lo = -1;
}
return lo;
}
#ifdef FEXT
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];
signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
freopen("KEK.out", "w", stdout);
int A, B, T, i;
int res;
FILE *f = fopen("KEK.inp", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d", &A);
if (res != 1)
fail("Failed to read A from input file.");
if (A < 0 || A > MAX_A)
fail("A is out of bounds.");
res = fscanf(f, "%d", &B);
if (res != 1)
fail("Failed to read B from input file.");
if (B < 0 || B > MAX_B)
fail("B is out of bounds.");
res = fscanf(f, "%d", &T);
if (res != 1)
fail("Failed to read T from input file.");
if (T < 1 || T > MAX_T)
fail("T is out of bounds.");
for (i = 0; i < A; i++) {
res = fscanf(f, "%d", &X[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < B; i++) {
res = fscanf(f, "%d", &Y[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < T; i++) {
res = fscanf(f, "%d%d", &W[i], &S[i]);
if (res != 2)
fail("Failed to read data from input file.");
}
fclose(f);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}
#endif
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |