Submission #595821

#TimeUsernameProblemLanguageResultExecution timeMemory
595821dooompyMP3 Player (CEOI10_mp3player)C++17
20 / 100
46 ms9480 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif #define int long long using ll = long long; char k[100005]; int t[100005]; int d[100005]; int s[100005]; int n, vm, v; struct node { int ls, rs, x; }; node tree[8 * 100005]; void combine(int x) { tree[x].ls = max(tree[2 * x].ls, tree[2 * x + 1].ls - tree[2 * x].x); tree[x].rs = min(tree[2 * x].rs, tree[ 2 * x + 1].rs - tree[2 * x].x); if (tree[x].ls <= tree[x].rs) { tree[x].x = tree[2 * x].x + tree[2 *x + 1].x; } else if (tree[2 * x].ls + tree[2*x].x > tree[2*x+1].rs) { tree[x] = {tree[2*x+1].rs, tree[2*x+1].rs, tree[2*x+1].x}; } else { tree[x] = {tree[2*x+1].ls, tree[2*x+1].ls, tree[2*x+1].x}; } } void build(int x, int l, int r) { tree[x] = {0, vm, 0}; if (l == r) { return; } int mid = (l + r) / 2; build(2*x, l, mid); build(2* x + 1, mid + 1, r); } void update(int x, int l, int r, int p) { if (l == r) { assert(p == l); if (k[p] == '+') { tree[x] = {0, vm-1, 1}; } else { tree[x] = {1, vm, -1}; } return; } int mid = (l + r) / 2; if (p <= mid) { update(2 * x, l, mid, p); } else { update(2 * x + 1, mid + 1, r, p); } combine(x); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); cin >> n >> vm >> v; assert(n <= 100000); for (int i = 0; i < n; i++) { cin >> k[i] >> t[i]; } for (int i = 0; i < n; i++) { d[i+1] = t[i+1] - t[i]; } for (int i = 0; i < n - 1;i ++) { s[i] = i + 1; } sort(s, s+n-1, [](int a, int b) { return d[a] < d[b]; }); // for (int i = 0; i < n-1; i++) { // cout << s[i] << endl; // } int offset = 1; while (offset < n) offset *= 2; for (int i = 0; i <= 2 * offset; i++) { tree[i] = {0, vm, 0}; } // build(1, 1, n-1); pair<int, int> ans = {-1, v}; for (int i = 0; i < n-1; i++) { assert(1 <= s[i] && s[i] <= n-1); int x = s[i] + offset; if (k[s[i]] == '+') { tree[x] = {0, vm - 1, 1}; } else { tree[x] = {1, vm, -1}; } while (x > 1) { x /= 2; tree[x].ls = max(tree[2 * x].ls, tree[2 * x + 1].ls - tree[2 * x].x); tree[x].rs = min(tree[2 * x].rs, tree[ 2 * x + 1].rs - tree[2 * x].x); if (tree[x].ls <= tree[x].rs) { tree[x].x = tree[2 * x].x + tree[2 *x + 1].x; } else if (tree[2 * x].ls + tree[2*x].x > tree[2*x+1].rs) { tree[x] = {tree[2*x+1].rs, tree[2*x+1].rs, tree[2*x+1].x}; } else { tree[x] = {tree[2*x+1].ls, tree[2*x+1].ls, tree[2*x+1].x}; } } // update(1, 1, n-1, s[i]); if(i == n - 2 || t[s[i]] != t[s[i + 1]]){ if(tree[1].ls + tree[1].x <= v && v < tree[1].rs + tree[1].x){ ans = {i, v - tree[1].x}; }else if(v == tree[1].rs + tree[1].x){ ans = {i, vm}; } } } if (ans.first == n-2) { cout << "infinity"; } else { cout << d[s[ans.first + 1]] - 1 << " " << ans.second; } }
#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...
#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...