Submission #966428

#TimeUsernameProblemLanguageResultExecution timeMemory
966428oviyan_gandhiExamination (JOI19_examination)C++17
2 / 100
3080 ms10636 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define int long long using namespace std; using namespace __gnu_pbds; typedef pair<int, int> pii; typedef tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oset; #define N 100000 #define S 320 pii s[N]; // {s, t} struct Query { int x, y, c, i; bool operator < (const Query &o) const { if (x/S != o.x/S) return x > o.x; return y < o.y; } }; Query qu[N]; int ans[N]; set<pii> st, disc; // {t, i} oset sc; // {s + t, i} int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; for (int i = 0; i < n; i++) cin >> s[i].first >> s[i].second; sort(s, s+n); for (int i = 0; i < q; i++){ cin >> qu[i].x >> qu[i].y >> qu[i].c; qu[i].i = i; qu[i].x = lower_bound(s, s+n, make_pair(qu[i].x, 0LL)) - s; } sort(qu, qu+q); int idx = n; for (int i = 0; i < q; i++){ while (idx-1 >= qu[i].x){ idx--; st.insert({s[idx].second, idx}); sc.insert({s[idx].first + s[idx].second, idx}); } while (idx < qu[i].x){ auto it = st.find({s[idx].second, idx}); if (it != st.end()){ st.erase(it); sc.erase({s[idx].first + s[idx].second, idx}); } else disc.erase({s[idx].second, idx}); idx++; } while (!st.empty() && st.begin()->first < qu[i].y){ int j = st.begin()->second; st.erase(st.begin()); sc.erase({s[j].first + s[j].second, j}); disc.insert({s[j].second, j}); } while (!disc.empty() && prev(disc.end())->first >= qu[i].y){ int j = prev(disc.end())->second; disc.erase(prev(disc.end())); st.insert({s[j].second, j}); sc.insert({s[j].first + s[j].second, j}); } ans[qu[i].i] = sc.size() - sc.order_of_key({qu[i].c, 0}); } for (int i = 0; i < q; i++) cout << ans[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...