oj.uz

Submission #154498

# Submission time Handle Problem Language Result Execution time Memory
154498 2019-09-22T10:07:57 Z FiloSanza Examination (JOI19_examination) C++14
0 / 100
 99 ms 6628 KB 
#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
*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 6628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 6628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -