Submission #370985

#TimeUsernameProblemLanguageResultExecution timeMemory
370985shivensinha4Robots (IOI13_robots)C++17
28 / 100
1144 ms19240 KiB
#include "bits/stdc++.h" #include"robots.h" #ifdef mlocal #include "grader.c" #endif using namespace std; #define for_(i, s, e) for (int i = s; i < (int) e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; #define long long int //#define endl '\n' // Ask for sum 1 -> n for full (one based indexing) class BIT { private: vector<ll> tree; int n = 1e6; int LSOne(int x) { return x&(-x); } public: void build(int x) { n = x; tree.resize(n+1); } ll sum(int a) { ll sum = 0; for (; a > 0; a -= LSOne(a)) sum += tree[a]; return sum; } ll sum(int a, int b) { return sum(b) - (a == 1 ? 0 : sum(a-1)); } void update(int p, ll v) { for (; p < n+1; p += LSOne(p)) tree[p] += v; } }; int a, b, t; vi wlim, slim; vector<ii> toys, toys2; BIT tree; bool check(ll box) { vi left, done; for (int i = t-1; i >= 0; i--) { int pt = lower_bound(slim.begin(), slim.end(), toys[i][1]) - slim.begin(); if (pt < b and tree.sum(pt+1, b) < box * (b-pt)) { tree.update(pt+1, 1); done.push_back(pt); } else left.push_back(i); } for (auto &i: done) tree.update(i+1, -1); done.clear(); bool valid = true; for (auto i: left) { int pt = lower_bound(wlim.begin(), wlim.end(), toys[i][0]) - wlim.begin(); if (pt < a and tree.sum(pt+1, a) < box * (a-pt)) { tree.update(pt+1, 1); done.push_back(pt); } else { valid = false; break; } } for (auto &i: done) tree.update(i+1, -1); return valid; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { a = A, b = B, t = T; wlim.reserve(A); slim.reserve(B); toys.reserve(T); for_(i, 0, a) { wlim.push_back(X[i]); wlim[i] -= 1; } for_(i, 0, b) { slim.push_back(Y[i]); slim[i] -= 1; } for_(i, 0, t) toys.push_back({W[i], S[i]}); toys2 = toys; for_(i, 0, t) swap(toys2[i][0], toys2[i][1]); sort(wlim.begin(), wlim.end()); sort(slim.begin(), slim.end()); sort(toys.begin(), toys.end()); for_(i, 0, t) if ((a == 0 or toys[i][0] > wlim.back()) and (b == 0 or toys[i][1] > slim.back())) return -1; tree.build(max(a, b)); int l = 0, r = T+1, ans = r; while (l < r) { int mid = (l+r)/2; bool fin = check(mid); if (fin) { ans = r = mid; } else l = mid+1; } return ans; }
#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...