Submission #674173

#TimeUsernameProblemLanguageResultExecution timeMemory
674173QwertyPiCambridge (info1cup18_cambridge)C++14
0 / 100
5 ms12756 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define pii pair<int, int> using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1e5 + 11; const int B = 800; int t[MAXN], d[MAXN]; int ans[MAXN], to[MAXN]; struct query{ int l, r, id; bool operator< (const query& o) const { if(l / B != o.l / B) return l / B < o.l / B; else if(r != o.r) return l / B % 2 == 0 ? r < o.r : r > o.r; else return id < o.id; } }; namespace DS{ struct SegTree{ int mx[MAXN << 3] = {0}, s[MAXN << 3] = {0}; void upd(int pos, int t, int d, int v, int tl, int tr){ if(tl == tr) { mx[v] = t - d, s[v] = t; return; } int tm = (tl + tr) / 2; if(pos <= tm){ upd(pos, t, d, v * 2 + 1, tl, tm); }else{ upd(pos, t, d, v * 2 + 2, tm + 1, tr); } mx[v] = max(mx[v * 2 + 1], s[v * 2 + 1] + mx[v * 2 + 2]); s[v] = s[v * 2 + 1] + s[v * 2 + 2]; } bool qry(){ return mx[0] < 0; } } segTree; int n; void init(int n){ DS::n = n; fill(segTree.mx, segTree.mx + (MAXN << 3), -(1 << 30)); fill(segTree.s, segTree.s + (MAXN << 3), 0); } void add(int idx){ // cout << "ADD " << idx << endl; idx = to[idx]; segTree.upd(idx, t[idx], d[idx], 0, 0, n - 1); } void del(int idx){ // cout << "DEL " << idx << endl; idx = to[idx]; segTree.upd(idx, 0, (1 << 30), 0, 0, n - 1); } int qry(){ // cout << "QRY" << endl; return segTree.qry(); } }; int ml[MAXN]; int32_t main(){ int n, m; cin >> n >> m; for(int i = 0; i < n; i++){ cin >> t[i] >> d[i]; } vector<pair<pair<int, int>, int>> v; for(int i = 0; i < n; i++){ v.push_back({{d[i], t[i]}, i}); } sort(v.begin(), v.end()); for(int i = 0; i < n; i++){ to[v[i].se] = i; d[i] = v[i].fi.fi; t[i] = v[i].fi.se; } int l = 0, r = -1; DS::init(n); for(int i = 0; i < n; i++){ DS::add(++r); cout << DS::qry() << endl; while(DS::qry() == 0){ DS::del(l++); } ml[r] = l; } for(int i = 0; i < m; i++){ int l, r; cin >> l >> r; l--; r--; cout << (l >= ml[r]) << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...