제출 #154498

#제출 시각아이디문제언어결과실행 시간메모리
154498FiloSanzaExamination (JOI19_examination)C++14
0 / 100
99 ms6628 KiB
#include <bits/stdc++.h> using namespace std; const int MAXX = 100010; struct fenwick{ int N; vector<int> v; fenwick(int sz){ N = sz; v.resize(N+10, 0); } void update(int pos){ if(pos < 0) return; for(pos+=2; pos<N; pos+=(pos&(-pos))) v[pos] ++; } int query(int pos){ int ans = 0; for(pos+=2; pos>0; pos-=(pos&(-pos))) ans += v[pos]; return ans; } int range(int a, int b){ return query(b) - query(a-1); } }; struct query_t{ int a, b, c, idx, ans; }; int main(){ cin.tie(0); cin.sync_with_stdio(0); int N, M; cin >> N >> M; vector<pair<int, int>> v(N); for(auto &i : v) cin >> i.first >> i.second; v.push_back({-1, -1}); sort(v.begin(), v.end()); vector<query_t> q(M); for(int i=0; i<M; i++) q[i].idx = i, cin >> q[i].a >> q[i].b >> q[i].c; sort(q.begin(), q.end(), [](const query_t& a, const query_t& b){ return a.a < b.a; }); int pos = M-1; fenwick fen(MAXX); for(int i=N; i>=0 && pos >= 0; i--){ fen.update(v[i].second); while(pos >= 0 && q[pos].a >= v[i].first){ q[pos].ans = fen.range(q[pos].b, MAXX); pos--; } } sort(q.begin(), q.end(), [](const query_t& a, const query_t& b){ return a.idx < b.idx; }); for(auto i : q) cout << i.ans << "\n"; } /* 5 4 35 100 70 70 45 15 80 40 20 95 20 50 0 10 10 0 60 60 0 0 100 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...