oj.uz

Submission #126864

# Submission time Handle Problem Language Result Execution time Memory
126864 2019-07-08T14:26:06 Z Osama_Alkhodairy Examination (JOI19_examination) C++17
41 / 100
 2896 ms 166264 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;

struct query{
    int A, B, ind;
};

int n, m;
vector <pair <int, int> > a;
vector <query> q[A];
vector <int> sum[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));
    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);
    }
    for(int i = 0 ; i < n ; i++){
        sum[a[i].first + a[i].second].push_back(i);
    }
    for(int i = 0 ; i < m ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        q[z].push_back({x, y, i});
    }
    vector <int> ans(m);
    for(int i = 0 ; i < A ; i++){
        if(i > 0){
            for(auto &j : sum[i - 1]){
                erase(0, n - 1, 1, j);
            }
        }
        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 &i : ans) cout << i << endl;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47224 KB Output is correct
2 Correct 61 ms 47328 KB Output is correct
3 Correct 61 ms 47292 KB Output is correct
4 Runtime error 120 ms 95532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2851 ms 164360 KB Output is correct
2 Correct 2896 ms 163980 KB Output is correct
3 Correct 2836 ms 164124 KB Output is correct
4 Correct 2226 ms 163556 KB Output is correct
5 Correct 1556 ms 163600 KB Output is correct
6 Correct 1529 ms 162120 KB Output is correct
7 Correct 2632 ms 163896 KB Output is correct
8 Correct 2572 ms 163904 KB Output is correct
9 Correct 2444 ms 163872 KB Output is correct
10 Correct 1163 ms 163520 KB Output is correct
11 Correct 1757 ms 163464 KB Output is correct
12 Correct 1270 ms 161672 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2851 ms 164360 KB Output is correct
2 Correct 2896 ms 163980 KB Output is correct
3 Correct 2836 ms 164124 KB Output is correct
4 Correct 2226 ms 163556 KB Output is correct
5 Correct 1556 ms 163600 KB Output is correct
6 Correct 1529 ms 162120 KB Output is correct
7 Correct 2632 ms 163896 KB Output is correct
8 Correct 2572 ms 163904 KB Output is correct
9 Correct 2444 ms 163872 KB Output is correct
10 Correct 1163 ms 163520 KB Output is correct
11 Correct 1757 ms 163464 KB Output is correct
12 Correct 1270 ms 161672 KB Output is correct
13 Correct 2539 ms 165412 KB Output is correct
14 Correct 2711 ms 165980 KB Output is correct
15 Correct 2838 ms 164564 KB Output is correct
16 Correct 2017 ms 165036 KB Output is correct
17 Correct 1416 ms 164936 KB Output is correct
18 Correct 1478 ms 163192 KB Output is correct
19 Correct 2527 ms 166264 KB Output is correct
20 Correct 2687 ms 166124 KB Output is correct
21 Correct 2418 ms 166204 KB Output is correct
22 Correct 1164 ms 163596 KB Output is correct
23 Correct 1720 ms 163692 KB Output is correct
24 Correct 1266 ms 161868 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47224 KB Output is correct
2 Correct 61 ms 47328 KB Output is correct
3 Correct 61 ms 47292 KB Output is correct
4 Runtime error 120 ms 95532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -