Submission #369625

#	Time	Username	Problem	Language	Result	Execution time	Memory
369625		79brue	Examination (JOI19_examination)	C++14	100 / 100	956 ms	81400 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
ll x[100002], y[100002];
ll qa[100002], qb[100002], qc[100002];
int ans[100002]; /// 아주 중요한 배열
bool chk[100002];

void solve1();
void solve2();
void solve3();
void solve4();

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &x[i], &y[i]);
    }
    for(int i=1; i<=q; i++){
        scanf("%lld %lld %lld", &qa[i], &qb[i], &qc[i]);
        ans[i] = n;
        if(qa[i] + qb[i] >= qc[i]) chk[i] = 1;
    }

    solve1();
    solve2();
    solve3();
    solve4();

    for(int i=1; i<=q; i++){
        printf("%d\n", ans[i]);
    }
}

void solve1(){
    vector<ll> vec;
    for(int i=1; i<=n; i++){
        vec.push_back(x[i]+y[i]);
    }
    sort(vec.begin(), vec.end());

    for(int i=1; i<=q; i++){
        ans[i] -= lower_bound(vec.begin(), vec.end(), qc[i]) - vec.begin();
    }
}

struct Node{
    Node *l, *r;
    ll s, e;
    int val;

    Node(ll _s, ll _e){
        l = r = nullptr;
        s = _s, e = _e;
        val = 0;
    }
    ~Node(){
        if(l) delete l;
        if(r) delete r;
    }

    void update(ll idx){
        if(s==e){
            val++;
            return;
        }
        ll m = (s+e)>>1;
        if(idx <= m){
            if(!l) l = new Node(s, m);
            l->update(idx);
        }
        else{
            if(!r) r = new Node(m+1, e);
            r->update(idx);
        }
        val++;
    }

    int sum(ll ts, ll te){
        if(e < ts || te < s) return 0;
        if(ts <= s && e <= te) return val;
        int ret = 0;
        if(l) ret += l->sum(ts, te);
        if(r) ret += r->sum(ts, te);
        return ret;
    }
};

struct segTree{
    Node* root;
    segTree(){
        root = new Node(0LL, 1000000000LL);
    }
    ~segTree(){
        delete root;
    }

    void update(int idx){
        root->update(idx);
    }
    int sum(ll s, ll e){
        return root->sum(s, e);
    }
};

struct Query{
    ll key; /// 정렬 기준이 될 것이다.
    int type; /// 0: 점 추가, 1: 쿼리 처리
    ll x; /// 점 추가일 경우: x좌표 (segment tree에서의 idx) | 쿼리 처리일 경우 x의 최댓값
    int idx; /// 쿼리 처리일 경우: 쿼리의 번호

    Query(){}
    Query(ll key, int type, ll x): key(key), type(type), x(x){}
    Query(ll key, int type, ll x, int idx): key(key), type(type), x(x), idx(idx){}

    bool operator<(const Query &r)const{
        if(key != r.key) return key>r.key;
        return type < r.type; /// 점 추가가 더 우선된다.
    }
};

void solve2(){
    /// x <= qa[i]-1, x+y >= qc[i] 인 것을 모두 찾는다.
    segTree tree;
    vector<Query> vec;

    for(int i=1; i<=n; i++){
        vec.push_back(Query(x[i]+y[i], 0, x[i]));
    }
    for(int i=1; i<=q; i++){
        if(!chk[i]){
            vec.push_back(Query(qc[i], 1, qa[i]-1, i));
        }
    }

    sort(vec.begin(), vec.end());
    for(Query query: vec){
        if(query.type == 0){ /// 점 추가 쿼리
            tree.update(query.x);
        }
        else{ /// 쿼리 답 구하기
            ans[query.idx] -= tree.sum(0, query.x);
        }
    }
}

void solve3(){
    /// y <= qb[i]-1, x+y >= qc[i] 인 것을 모두 찾는다.
    segTree tree;
    vector<Query> vec;

    for(int i=1; i<=n; i++){
        vec.push_back(Query(x[i]+y[i], 0, y[i]));
    }
    for(int i=1; i<=q; i++){
        if(!chk[i]){
            vec.push_back(Query(qc[i], 1, qb[i]-1, i));
        }
    }

    sort(vec.begin(), vec.end());
    for(Query query: vec){
        if(query.type == 0){ /// 점 추가 쿼리
            tree.update(query.x);
        }
        else{ /// 쿼리 답 구하기
            ans[query.idx] -= tree.sum(0, query.x);
        }
    }
}

void solve4(){
    /// 특수한 경우의 해를 빠르게 찾는다.
    segTree tree;
    vector<Query> vec;

    for(int i=1; i<=n; i++){
        vec.push_back(Query(y[i], 0, x[i]));
    }
    for(int i=1; i<=q; i++){
        if(chk[i]){
            vec.push_back(Query(qb[i], 1, qa[i], i));
        }
    }

    sort(vec.begin(), vec.end(), [&](auto p1, auto p2){
        if(p1.key != p2.key) return p1.key > p2.key;
        return p1.type < p2.type;
    });

    for(Query query: vec){
        if(query.type == 0){
            tree.update(query.x);
        }
        else{
            ans[query.idx] = tree.sum(query.x, 1000000000);
        }
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         scanf("%lld %lld", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%lld %lld %lld", &qa[i], &qb[i], &qc[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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