제출 #154512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154512		FiloSanza	Examination (JOI19_examination)	C++14	0 / 100	96 ms	6504 KiB

examination

#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--){
        if(i != 0) fen.update(v[i].second);
        while(i > 0 && v[i-1].first == v[i].first)
            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
20 95
35 100
45 15
70 70
80 40
20 50 0
10 10 0
60 60 0
0 100 0
*/

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57