Submission #485628

#TimeUsernameProblemLanguageResultExecution timeMemory
485628tibinyteCambridge (info1cup18_cambridge)C++14
0 / 100
0 ms204 KiB
#include<bits/stdc++.h> #define mod 1000000007 #define inf 1e17 using namespace std; struct aint { vector<long long> a; vector<long long> lazy; void prop(long long node, long long left, long long right) { a[node] += lazy[node]; if (left != right) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[2 * node + 1], lazy[node]; } lazy[node] = 0; } void build(vector<long long>& b, long long node, long long left, long long right) { if ((long long)a.size() == 0) { long long n = b.size() - 1; a = vector<long long>(4 * n); lazy = vector<long long>(4 * n); } if (left == right) { a[node] = b[left]; } else { long long mid = (left + right) / 2; build(b, 2 * node, left, mid); build(b, 2 * node + 1, mid + 1, right); a[node] = min(a[2 * node], a[2 * node + 1]); } } long long query(long long node, long long left, long long right, long long st, long long dr) { if (left > right) { return 2 * inf; } prop(node, left, right); if (st <= left && dr >= right) { return a[node]; } if ((st<left || st>right) && (dr<left || dr>right)) { return 2 * inf; } long long mid = (left + right) / 2; return min(query(2 * node, left, mid, st, dr), query(2 * node + 1, mid + 1, right, st, dr)); } void update(long long node, long long left, long long right, long long st, long long dr, long long val) { if (left > right) { return; } prop(node, left, right); if (st <= left && dr >= right) { lazy[node] += val; return; } if ((st<left || st>right) && (dr<left || dr>right)) { return; } long long mid = (left + right) / 2; update(2 * node, left, mid, st, dr, val); update(2 * node + 1, mid + 1, right, st, dr, val); prop(2 * node, left, mid); prop(2 * node + 1, mid + 1, right); a[node] = min(a[2 * node], a[2 * node + 1]); } }; vector<pair<long long, long long>> a; map<pair<long long, long long>, long long> poz; long long n, q; aint tree; void add(long long ind) { long long wh = poz[a[ind]]; tree.update(1, 1, n, wh, wh, -inf + a[ind].first); tree.update(1, 1, n, wh, n, -a[ind].second); } void rem(long long ind) { long long wh = poz[a[ind]]; tree.update(1, 1, n, wh, wh, inf); tree.update(1, 1, n, wh, n, a[ind].second); } int main() { std::ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; a = vector<pair<long long, long long>>(n + 1); vector<pair<long long, long long>> norm(n + 1); for (long long i = 1; i <= n; ++i) { cin >> a[i].second >> a[i].first; norm[i] = a[i]; } sort(norm.begin() + 1, norm.end()); for (long long i = 1; i <= n; ++i) { poz[norm[i]] = i; } vector<long long> values(n + 1); for (long long i = 1; i <= n; ++i) { values[i] = inf; } tree.build(values, 1, 1, n); long long p = 0; vector<long long> right(n + 1); for (long long i = 1; i <= n; ++i) { if (i > 1) { rem(i - 1); } if (p == i - 1) { p++; } while (p <= n) { add(p); if (tree.query(1, 1, n, 1, n) <= 0) { rem(p); break; } p++; } right[i] = p - 1; } while (q--) { long long st, dr; cin >> st >> dr; if (right[st] < dr) { cout << 0 << '\n'; } else { cout << 1 << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...