oj.uz

Submission #126851

# Submission time Handle Problem Language Result Execution time Memory
126851 2019-07-08T14:05:49 Z Osama_Alkhodairy Examination (JOI19_examination) C++17
20 / 100
 2248 ms 155000 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 100001;
const int A = 200001;
const int INF = (int)1e9;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, m;
vector <pair <int, int> > a, q[A];
ordered_set v[4 * N];

void insert(ordered_set &s, int v){
    auto it = s.upper_bound(make_pair(v, INF));
    if(it == s.begin()){
        s.insert(make_pair(v, 0));
        return;
    }
    it--;
    if(it == s.end() || (*it).first != v) s.insert(make_pair(v, 0));
    else s.insert(make_pair(v, (*it).second + 1));
}
void erase(ordered_set &s, int v){
    auto it = s.upper_bound(make_pair(v, INF));
    it--;
    s.erase(it);
}
void update(int l, int r, int node, int ind, int val){
    if(r < l || l > ind || r < ind) return;
    insert(v[node], val);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(ind <= mid) update(l, mid, 2 * node, ind, val);
    update(mid + 1, r, 2 * node + 1, ind, val);
}
int query(int l, int r, int node, int s, int e, int val){
    if(r < l || r < s || l > e) return 0;
    if(s <= l && r <= e){
        return (int)v[node].size() - v[node].order_of_key(make_pair(val, -INF));
    }
    int mid = (l + r) / 2;
    return query(l, mid, 2 * node, s, e, val) + query(mid + 1, r, 2 * node + 1, s, e, val);
}
int query(int suffix, int val){
    return query(0, n - 1, 1, suffix, n - 1, val);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    a.resize(n);
    for(auto &i : a) cin >> i.first >> i.second;
    sort(a.begin(), a.end());
    for(int i = 0 ; i < n ; i++){
        update(0, n - 1, 1, i, a[i].second);
    }
    for(int i = 0 ; i < m ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        int suff = lower_bound(a.begin(), a.end(), make_pair(x, -INF)) - a.begin();
        if(suff == n){
            cout << 0 << endl;
            continue;
        }
        cout << query(suff, y) << endl;
    }
}

Subtask #1
0 / 2.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2183 ms 154964 KB Output is correct
2 Correct 2177 ms 154996 KB Output is correct
3 Correct 2248 ms 154908 KB Output is correct
4 Correct 2023 ms 155000 KB Output is correct
5 Correct 1528 ms 155000 KB Output is correct
6 Correct 1487 ms 154872 KB Output is correct
7 Correct 2057 ms 154948 KB Output is correct
8 Correct 1921 ms 155000 KB Output is correct
9 Correct 1803 ms 154956 KB Output is correct
10 Correct 1177 ms 154616 KB Output is correct
11 Correct 1646 ms 154872 KB Output is correct
12 Correct 1106 ms 154488 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2183 ms 154964 KB Output is correct
2 Correct 2177 ms 154996 KB Output is correct
3 Correct 2248 ms 154908 KB Output is correct
4 Correct 2023 ms 155000 KB Output is correct
5 Correct 1528 ms 155000 KB Output is correct
6 Correct 1487 ms 154872 KB Output is correct
7 Correct 2057 ms 154948 KB Output is correct
8 Correct 1921 ms 155000 KB Output is correct
9 Correct 1803 ms 154956 KB Output is correct
10 Correct 1177 ms 154616 KB Output is correct
11 Correct 1646 ms 154872 KB Output is correct
12 Correct 1106 ms 154488 KB Output is correct
13 Incorrect 2145 ms 154812 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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