oj.uz

Submission #873551

# Submission time Handle Problem Language Result Execution time Memory
873551 2023-11-15T09:44:33 Z NintsiChkhaidze Examination (JOI19_examination) C++17
0 / 100
 3000 ms 92920 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/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
namespace __gnu_pbds{
          typedef tree<long long,
                       null_type,
                       less_equal<long long>,
                       rb_tree_tag,
                       tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;

using namespace std;
const int N = 2e5 + 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

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<long long int, __gnu_pbds::null_type, std::less_equal<long long int>, __gnu_pbds::detail::tree_traits<long long int, __gnu_pbds::null_type, std::less_equal<long long 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.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 79448 KB Output is correct
2 Correct 42 ms 79448 KB Output is correct
3 Correct 42 ms 79188 KB Output is correct
4 Correct 48 ms 79192 KB Output is correct
5 Correct 44 ms 79388 KB Output is correct
6 Correct 41 ms 79188 KB Output is correct
7 Correct 1846 ms 83324 KB Output is correct
8 Correct 1812 ms 83204 KB Output is correct
9 Correct 1774 ms 83472 KB Output is correct
10 Correct 1415 ms 83300 KB Output is correct
11 Execution timed out 3035 ms 81728 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 79448 KB Output is correct
2 Correct 42 ms 79448 KB Output is correct
3 Correct 42 ms 79188 KB Output is correct
4 Correct 48 ms 79192 KB Output is correct
5 Correct 44 ms 79388 KB Output is correct
6 Correct 41 ms 79188 KB Output is correct
7 Correct 1846 ms 83324 KB Output is correct
8 Correct 1812 ms 83204 KB Output is correct
9 Correct 1774 ms 83472 KB Output is correct
10 Correct 1415 ms 83300 KB Output is correct
11 Execution timed out 3035 ms 81728 KB Time limit exceeded
12 Halted 0 ms 0 KB -