oj.uz

Submission #126879

# Submission time Handle Problem Language Result Execution time Memory
126879 2019-07-08T14:44:29 Z Osama_Alkhodairy Examination (JOI19_examination) C++17
2 / 100
 3000 ms 160596 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)2e9;
 
#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;
 
struct query{
    int A, B, ind;
};
 
int n, m;
vector <pair <int, int> > a;
map <int, vector <query> > q;
map <int, vector <int> > sum;
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));
    assert(it != s.begin());
    it--;
    assert((*it).first == v);
    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);
}
void erase(int l, int r, int node, int ind){
    if(r < l) return;
    erase(v[node], a[ind].second);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(ind <= mid) erase(l, mid, 2 * node, ind);
    else erase(mid + 1, r, 2 * node + 1, ind);
}
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);
    }
    vector <int> all;
    for(int i = 0 ; i < n ; i++){
        sum[a[i].first + a[i].second].push_back(i);
        all.push_back(a[i].first + a[i].second);
    }
    for(int i = 0 ; i < m ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        q[z].push_back({x, y, i});
        all.push_back(z);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    vector <int> ans(m);
    for(auto &i : all){
        for(auto &j : q[i]){
            int suff = lower_bound(a.begin(), a.end(), make_pair(j.A, -INF)) - a.begin();
            if(suff == n) ans[j.ind] = 0;
            else ans[j.ind] = query(suff, j.B);
        }
        for(auto &j : sum[i]){
            erase(0, n - 1, 1, j);
        }
    }
    for(auto &i : ans) cout << i << endl;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 37880 KB Output is correct
2 Correct 51 ms 37904 KB Output is correct
3 Correct 50 ms 37832 KB Output is correct
4 Correct 50 ms 37856 KB Output is correct
5 Correct 50 ms 37880 KB Output is correct
6 Correct 51 ms 37856 KB Output is correct
7 Correct 86 ms 41040 KB Output is correct
8 Correct 87 ms 41152 KB Output is correct
9 Correct 89 ms 41052 KB Output is correct
10 Correct 85 ms 41160 KB Output is correct
11 Correct 84 ms 41208 KB Output is correct
12 Correct 80 ms 40440 KB Output is correct
13 Correct 89 ms 40808 KB Output is correct
14 Correct 101 ms 40892 KB Output is correct
15 Correct 87 ms 40876 KB Output is correct
16 Correct 76 ms 40900 KB Output is correct
17 Correct 79 ms 41080 KB Output is correct
18 Correct 77 ms 40440 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 160596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 160596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 37880 KB Output is correct
2 Correct 51 ms 37904 KB Output is correct
3 Correct 50 ms 37832 KB Output is correct
4 Correct 50 ms 37856 KB Output is correct
5 Correct 50 ms 37880 KB Output is correct
6 Correct 51 ms 37856 KB Output is correct
7 Correct 86 ms 41040 KB Output is correct
8 Correct 87 ms 41152 KB Output is correct
9 Correct 89 ms 41052 KB Output is correct
10 Correct 85 ms 41160 KB Output is correct
11 Correct 84 ms 41208 KB Output is correct
12 Correct 80 ms 40440 KB Output is correct
13 Correct 89 ms 40808 KB Output is correct
14 Correct 101 ms 40892 KB Output is correct
15 Correct 87 ms 40876 KB Output is correct
16 Correct 76 ms 40900 KB Output is correct
17 Correct 79 ms 41080 KB Output is correct
18 Correct 77 ms 40440 KB Output is correct
19 Execution timed out 3031 ms 160596 KB Time limit exceeded
20 Halted 0 ms 0 KB -