제출 #373752

#제출 시각아이디문제언어결과실행 시간메모리
373752morato로봇 (IOI13_robots)C++17
0 / 100
53 ms65540 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; const int N = 1050000; const int M = 500005; const int INF = 1e9; struct Node { pair<int, int> mn; // valor, indice pair<int, int> mx; // valor, indice Node() { mn = {INF, 0}; mx = {-1, 0}; } Node(pair<int, int> a, pair<int, int> b): mn(a), mx(b) {} Node operator+(Node other) { return Node(min(mn, other.mn), max(mx, other.mx)); } }; struct SegTree { Node seg[4 * N]; void update(int node, int l, int r, pair<int, int> x) { // cout << node << ' ' << l << ' ' << r << " {" << x.first << ", " << x.second << "}\n"; if (l == r) { //assert(l == x.second); // cout << seg[node].mn.first << " -> " << x.first << '\n'; seg[node] = Node(x, x); } else { int m = (l + r) >> 1; if (x.second <= m) { update(2 * node, l, m, x); } else { update(2 * node + 1, m + 1, r, x); } seg[node] = seg[2 * node] + seg[2 * node + 1]; } } Node query(int node, int l, int r, int ql, int qr) { if (ql > r || l > qr) { return Node({INF, 0}, {-1, 0}); } if (ql <= l && r <= qr) { // cout << seg[node].mn.first << " " << seg[node].mn.second << '\n'; return seg[node]; } int m = (l + r) >> 1; return query(2 * node, l, m, ql, qr) + query(2 * node + 1, m + 1, r, ql, qr); } } seg_weak, seg_small; vector<pair<int, pair<int, int>>> compress[2]; // comprimir pesos e alturas /* int A, B, T, X[M], Y[M], W[N], S[N]; void read() { cin >> A >> B >> T; for (int i = 0; i < A; i++) cin >> X[i]; for (int i = 0; i < B; i++) cin >> Y[i]; for (int i = 0; i < T; i++) { cin >> W[i] >> S[i]; } }*/ int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { /*int main() { ios::sync_with_stdio(false); cin.tie(0); read();*/ for (int i = 0; i < A; i++) { compress[0].push_back({X[i], {0, i}}); } for (int i = 0; i < B; i++) { compress[1].push_back({Y[i], {0, i}}); } for (int i = 0; i < T; i++) { compress[0].push_back({W[i], {1, i}}); compress[1].push_back({S[i], {1, i}}); } sort(compress[0].begin(), compress[0].end()); sort(compress[1].begin(), compress[1].end()); for (int i = 0; i < (int) compress[0].size(); i++) { if (compress[0][i].second.first) { W[compress[0][i].second.second] = i + 1; } else { X[compress[0][i].second.second] = i + 1; } } for (int i = 0; i < (int) compress[1].size(); i++) { if (compress[1][i].second.first) { S[compress[1][i].second.second] = i + 1; } else { Y[compress[1][i].second.second] = i + 1; } } int n = (int) compress[0].size(); int m = (int) compress[1].size(); for (int i = 0; i < A; i++) { pair<int, int> valor(0, X[i]); seg_weak.update(1, 1, n, valor); } for (int i = 0; i < B; i++) { // cout << Y[i] << ' '; pair<int, int> valor(0, Y[i]); seg_small.update(1, 1, m, valor); } // cout << '\n'; for (int i = 0; i < T; i++) { Node weak = seg_weak.query(1, 1, n, W[i] + 1, n); Node small = seg_small.query(1, 1, m, S[i] + 1, m); // cout << "WEAK [" << W[i] << ", " << n << "] = " << weak.mn.first << "(" << weak.mn.second << ")\n"; // cout << "SMALL [" << S[i] << ", " << m << "] = " << small.mn.first << "(" << small.mn.second << ")\n"; // cout << '\n'; if (weak.mn.first == INF && small.mn.first == INF) { // cout << "DEU BOSTA\n"; // break; return -1; } else if (weak.mn.first < small.mn.first) { pair<int, int> novo(weak.mn.first + 1, weak.mn.second); seg_weak.update(1, 1, n, novo); } else { // cout << small.mn.first << " -> " << small.mn.first + 1 << '\n'; pair<int, int> novo(small.mn.first + 1, small.mn.second); seg_small.update(1, 1, m, novo); } } return max(seg_weak.seg[1].mx.first, seg_small.seg[1].mx.first); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...