| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1166220 | sano | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
#include "robots.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
bool check(int a, int b, int t, vec<int>&x, vec<int>&y, vec<pii> v, int mid) {
map<int, int> umap;
set<int> s;
For(i, b) {
umap[y[i]] += mid;
s.insert(y[i]);
}
vec<pii> nv;
rfor(i, t - 1) {
auto poz = s.upper_bound(v[i].ss);
if (poz == s.end()) { continue; }
umap[*poz]--;
if (umap[*poz] == 0) s.erase(poz);
swap(v.back(), v[i]);
v.pop_back();
}
sort(v.begin(), v.end());
int mam = mid;
int som = a - 1;
while (som >= 0) {
if (v.empty()) return 1;
if (v.back().ff >= x[som]) return 0;
v.pop_back(); mam--;
if (mam == 0) som--;
}
if (v.empty()) return 1;
return 0;
}
int putaway(int a, int b, int t, int x1[], int y1[], int w1[], int s1[]) {
vec<int> x, y;
vec<pii> v;
For(i, a) x.push_back(x1[i]);
For(i, b) y.push_back(y1[i]);
For(i, t) v.push_back({ w1[i], s1[i] });
sort(x.begin(), x.end()); sort(y.begin(), y.end());
sort(v.begin(), v.end());
int l = 1, r = t;
while (l < r) {
int mid = (l + r) / 2;
if (check(a, b, t, x, y, v, mid)) r = mid;
else l = mid + 1;
}
if (!check(a, b, t, x, y, v, l)) return -1;
return l;
}
signed main() {
ll t;
//cin >> t;
t = 1;
For(ww, t) {
int a, b, t;
cin >> a >> b >> t;
int x[10], y[10], w[10], s[10];
For(i, a) cin >> x[i];
For(i, b) cin >> y[i];
For(i, t) cin >> w[i] >> s[i];
cout << putaway(a, b, t, x, y, w, s) << '\n';
}
return 0;
}