제출 #373753

#제출 시각아이디문제언어결과실행 시간메모리
373753morato로봇 (IOI13_robots)C++17
0 / 100
49 ms65540 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; const int N = 2000000; const int M = 500005; const int INF = 1e9; struct Node { pair<int, int> mn; pair<int, int> mx; 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) { if (l == r) { 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) { 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]; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { 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++) { pair<int, int> valor(0, Y[i]); seg_small.update(1, 1, m, valor); } 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); if (weak.mn.first == INF && small.mn.first == INF) { 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 { 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...