oj.uz

Submission #126897

# Submission time Handle Problem Language Result Execution time Memory
126897 2019-07-08T15:02:38 Z Osama_Alkhodairy Examination (JOI19_examination) C++17
20 / 100
 3000 ms 166836 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, x[N], y[N], z[N];
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);
    }
    vector <pair <int, pair <int, int> > > all;
    for(int i = 0 ; i < n ; i++){
        all.push_back(make_pair(a[i].first + a[i].second, make_pair(1, i)));
        sum[a[i].first + a[i].second].push_back(i);
    }
    for(int i = 0 ; i < m ; i++){
        cin >> x[i] >> y[i] >> z[i];
        all.push_back(make_pair(z[i], make_pair(0, i)));
    }
    vector <int> ans(m);
    sort(all.begin(), all.end());
    for(auto &i : all){
        if(i.second.first == 1) erase(0, n - 1, 1, i.second.second);
        else{
            int j = i.second.second;
            int suff = lower_bound(a.begin(), a.end(), make_pair(x[j], -INF)) - a.begin();
            if(suff == n) ans[j] = 0;
            else ans[j] = query(suff, y[j]);
        }
    }
    for(auto &i : ans) cout << i << endl;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47324 KB Output is correct
2 Correct 60 ms 47352 KB Output is correct
3 Correct 60 ms 47352 KB Output is correct
4 Runtime error 115 ms 95640 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 2971 ms 166604 KB Output is correct
2 Correct 2935 ms 166836 KB Output is correct
3 Correct 2954 ms 166668 KB Output is correct
4 Correct 2441 ms 165624 KB Output is correct
5 Correct 1571 ms 165540 KB Output is correct
6 Correct 1545 ms 164152 KB Output is correct
7 Correct 2805 ms 165892 KB Output is correct
8 Correct 2680 ms 166028 KB Output is correct
9 Correct 2594 ms 166020 KB Output is correct
10 Correct 1187 ms 165608 KB Output is correct
11 Correct 1723 ms 165592 KB Output is correct
12 Correct 1284 ms 163840 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2971 ms 166604 KB Output is correct
2 Correct 2935 ms 166836 KB Output is correct
3 Correct 2954 ms 166668 KB Output is correct
4 Correct 2441 ms 165624 KB Output is correct
5 Correct 1571 ms 165540 KB Output is correct
6 Correct 1545 ms 164152 KB Output is correct
7 Correct 2805 ms 165892 KB Output is correct
8 Correct 2680 ms 166028 KB Output is correct
9 Correct 2594 ms 166020 KB Output is correct
10 Correct 1187 ms 165608 KB Output is correct
11 Correct 1723 ms 165592 KB Output is correct
12 Correct 1284 ms 163840 KB Output is correct
13 Correct 2771 ms 165912 KB Output is correct
14 Execution timed out 3063 ms 165768 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47324 KB Output is correct
2 Correct 60 ms 47352 KB Output is correct
3 Correct 60 ms 47352 KB Output is correct
4 Runtime error 115 ms 95640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -