제출 #873533

#제출 시각아이디문제언어결과실행 시간메모리
873533NintsiChkhaidzeExamination (JOI19_examination)C++17
2 / 100
3091 ms37280 KiB
#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>
#define int ll
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){
    if (!x.size()) return y;
    if (!y.size()) return x;

    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],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<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].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;
}

컴파일 시 표준 에러 (stderr) 메시지

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