Submission #873529

#	Time	Username	Problem	Language	Result	Execution time	Memory
873529		NintsiChkhaidze	Examination (JOI19_examination)	C++17	0 / 100	3096 ms	25756 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>
using namespace std;

const int N = 1e5 + 5;

int S[N],T[N],X[N],Y[N],Z[N],ans[N];
map <int,int> mp;
vector <int> v[4*N];
vector <int> merge(vector <int> x, vector <int> y){

    int l1=0,l2=0;
    vector <int> vnew;
    for (int i = 0; i < (int)x.size() + (int)y.size(); i++){
        if (l1 == x.size()){
            vnew.pb(y[l2++]);
            continue;
        }

        if (l2 == y.size()){
            vnew.pb(x[l1++]);
            continue;
        }

        if (x[l1] < y[l2]) {
            vnew.pb(x[l1++]);
        }else{
            vnew.pb(y[l2++]);
        }
    }
    return vnew;
}
void upd(int h,int l,int r,int idx,int val){
    if (l == r){
        int len = v[h].size(),l = 0;

        vector <int> vnew;
        for (int i=0;i<=len;i++){
            if (val == -1){
                vnew.pb(v[h][l++]);
                continue;
            }
            if (l < len && v[h][l] < val) {
                vnew.pb(v[h][l++]);
            }else{
                vnew.pb(val);
                val = -1;
            }
        }

        v[h] = vnew;
        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 le = 0,ri = v[h].size() - 1,res=-1;
        while (le <= ri){
            int mid = (le + ri)/2;
            if (v[h][mid] >= k){
                res = mid;
                ri = mid - 1;
            }else{
                le = mid + 1;
            }
        }

        if (res == -1) return 0;
        return (int)v[h].size() - res;
    }
    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],i},1});
    }

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

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

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

    for (int i=vec.size()-1;i>=0;i--){
        int id = vec[i].f.s;

        if (vec[i].s == 1){
            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]);
            //Y[id] ze meti an tolebis raodenoba
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<ans[i]<<endl;
}

Compilation message (stderr)

examination.cpp: In function 'std::vector<int> merge(std::vector<int>, std::vector<int>)':
examination.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         if (l1 == x.size()){
      |             ~~~^~~~~~~~~~~
examination.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (l2 == y.size()){
      |             ~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i=0;i<v1.size();i++){
      |                  ~^~~~~~~~~~

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