Submission #873555

#	Time	Username	Problem	Language	Result	Execution time	Memory
873555		NintsiChkhaidze	Examination (JOI19_examination)	C++17	0 / 100	3051 ms	5448 KiB

examination

#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/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
namespace __gnu_pbds{
          typedef tree<int,
                       null_type,
                       less_equal<int>,
                       rb_tree_tag,
                       tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;

using namespace std;
const int N = 6000 + 5;

int S[N],T[N],X[N],Y[N],Z[N],ans[N];
int L,R,k;
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){
    if (l == r){
        v[h].insert(R);
        return;
    }
    if (L > (l + r)/2) upd(right);
    else upd(left);
    v[h] = merge(v[h*2],v[h*2 + 1]);
}

int get(int h,int l,int r){
    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) + get(right);
}
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){
            L = mp[S[id]];
            R = T[id];
            upd(1,1,n + q);
        }else{
            L = mp[X[id]];
            R = n + q;
            k = Y[id];
            ans[id] = get(1,1,n + q);
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<ans[i]<<endl;
}

Compilation message (stderr)

examination.cpp: In function '__gnu_pbds::ordered_set merge(__gnu_pbds::ordered_set, __gnu_pbds::ordered_set)':
examination.cpp:33: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_equal<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less_equal<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]
   33 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57