oj.uz

Submission #873539

# Submission time Handle Problem Language Result Execution time Memory
873539 2023-11-15T09:34:21 Z NintsiChkhaidze Examination (JOI19_examination) C++17
0 / 100
 3000 ms 79384 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l + r)>>1) + 1,r
#define pii pair<int,int>

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 


using namespace std;

const int N = 2e5 + 5;

int S[N],T[N],X[N],Y[N],Z[N],ans[N];
map <int,int> mp;
ordered_set v[4*N];

ordered_set merge(ordered_set x, ordered_set y){
    if (x.size() > y.size()) swap(x,y);
    for (int i = 0; i < x.size(); i++)
        y.insert(*(x.find_by_order(i)));
    return y;
}

void upd(int h,int l,int r,int idx,int val){
    if (l == r){
        v[h].insert(val);
        return;
    }

    if (idx > (l + r)/2) upd(right,idx,val);
    else upd(left,idx,val);
    v[h] = merge(v[h*2],v[h*2 + 1]);
}

int get(int h,int l,int r,int L,int R,int k){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R){
        int len = v[h].size();
        return len - v[h].order_of_key(k);
    }
    return get(left,L,R,k) + get(right,L,R,k);
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,q;
    cin>>n>>q;

    vector <int> v1;
    vector <pair<pii,int> > vec;
    for (int i = 1; i <= n; i++){
        cin >> S[i] >> T[i];
        v1.pb(S[i]);
        vec.pb({{S[i] + T[i],2},i});
    }

    for (int i = 1; i <= q; i++){
        cin >> X[i] >> Y[i] >> Z[i];
        v1.pb(X[i]);
        vec.pb({{Z[i],1},i});
    }

    sort(vec.begin(),vec.end());
    sort(v1.begin(),v1.end());

    int val = 0;
    for (int i=0;i<(int)v1.size();i++){
        if (!i || v1[i] != v1[i - 1]) ++val;
        mp[v1[i]] = val;
    }

    for (int i=(int)vec.size()-1;i>=0;i--){
        int id = vec[i].s;
        if (vec[i].f.s == 2){
            upd(1,1,n + q,mp[S[id]],T[id]);
        }else{
            ans[id] = get(1,1,n + q,mp[X[id]],n + q,Y[id]);
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<ans[i]<<endl;
}

Compilation message

examination.cpp: In function '__gnu_pbds::tree<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> merge(__gnu_pbds::tree<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>, __gnu_pbds::tree<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>)':
examination.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66664 KB Output is correct
2 Correct 46 ms 66908 KB Output is correct
3 Correct 40 ms 66900 KB Output is correct
4 Correct 39 ms 66868 KB Output is correct
5 Correct 37 ms 66908 KB Output is correct
6 Correct 38 ms 66904 KB Output is correct
7 Correct 1795 ms 69872 KB Output is correct
8 Correct 1836 ms 69712 KB Output is correct
9 Correct 1756 ms 69760 KB Output is correct
10 Incorrect 96 ms 68176 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 79384 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 3039 ms 79384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66664 KB Output is correct
2 Correct 46 ms 66908 KB Output is correct
3 Correct 40 ms 66900 KB Output is correct
4 Correct 39 ms 66868 KB Output is correct
5 Correct 37 ms 66908 KB Output is correct
6 Correct 38 ms 66904 KB Output is correct
7 Correct 1795 ms 69872 KB Output is correct
8 Correct 1836 ms 69712 KB Output is correct
9 Correct 1756 ms 69760 KB Output is correct
10 Incorrect 96 ms 68176 KB Output isn't correct
11 Halted 0 ms 0 KB -