제출 #877187

#제출 시각아이디문제언어결과실행 시간메모리
877187vjudge1Examination (JOI19_examination)C++17
2 / 100
3063 ms44340 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 10, MOD = 1e9 + 7;

int n,q,s[N],t[N],x[N],y[N],z[N],sm[N],res[N];
vector<int> a,p,qq;
struct segtree{
    int t[N * 4];
    void build(int v = 1,int tl = 1,int tr = N){
        t[v] =0 ;
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
    }
    void upd(int pos,int val,int v = 1,int tl = 1,int tr = N){
        if(tl == tr){
            t[v] += val;
        }else{
            int tm = (tl + tr) >> 1;
            if(pos <= tm) upd(pos,val,v+v,tl,tm);
            else upd(pos,val,v+v+1,tm+1,tr);
            t[v] = t[v + v] + t[v + v + 1];
        }
    }
    int get(int l,int r,int v = 1,int tl = 1,int tr = N){
        if(l > r || tl > r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
}A,B;
int find(int val){
    int it = lower_bound(a.begin(),a.end(),val) - a.begin();
    return it + 1;
}
bool cmp(int i,int j){
    return (sm[i] > sm[j]);
}
bool cmp1(int i,int j){
    return (z[i] > z[j]);
}
void test(){
    A.build();
    B.build();
    cin >> n >> q;
    p.resize(n);
    iota(p.begin(),p.end(),1);
    qq.resize(q);
    iota(qq.begin(),qq.end(),1);
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> t[i];
        sm[i] = s[i] + t[i];
        a.push_back(s[i]);
        a.push_back(t[i]);
        a.push_back(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        cin >> x[i] >> y[i] >> z[i];
        a.push_back(x[i]);
        a.push_back(y[i]);
        a.push_back(z[i]);
    }
    sort(a.begin(),a.end());
    for(int i = 1;i <= n;i++){
        s[i] = find(s[i]);t[i] = find(t[i]);sm[i] = find(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        x[i] = find(x[i]);y[i] = find(y[i]);z[i] = find(z[i]);
    }
    sort(p.begin(),p.end(),cmp);
    sort(qq.begin(),qq.end(),cmp1);
    int it = 0;
    vector<pair<int,int>> f;
    for(int i:qq){
        while(it < p.size() && sm[p[it]] >= z[i]){
            A.upd(s[p[it]],1);
            B.upd(t[p[it]],1);
            f.push_back({s[p[it]],t[p[it]]});
            it++;
        }
        int col  =0;
        for(auto [a,b]:f){
            if(a >= x[i] && b >= y[i]){
                col++;
            }
        }
        res[i] = col;
    }
    for(int i = 1;i <= q;i++){
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

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

examination.cpp: In function 'void test()':
examination.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(it < p.size() && sm[p[it]] >= z[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...