Submission #104513

#	Time	Username	Problem	Language	Result	Execution time	Memory
104513		onjo0127	Examination (JOI19_examination)	C++11	100 / 100	327 ms	16824 KiB

examination

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
#define all(v) v.begin(), v.end()

struct fenwick {
    vector<int> T; int sz;
    fenwick(int N) { sz = N; T.resize(N + 1); }
    void upd(int x) {
        for(int i=x; i<=sz; i+=(i&-i)) ++T[i];
    }
    int get(int x) {
        int s = 0;
        for(int i=x; i>=1; i-=(i&-i)) s += T[i];
        return s;
    }
    int sum(int l, int r) {
        return get(r) - get(l-1);
    }
};
struct q1 { int x, y, z, ty, id; };
struct q2 { int x, y, ty, id; };

pii A[100009];
int ans[100009];
vector<int> xs, ys;

inline int getx(int x) { return lower_bound(all(xs), x) - xs.begin() + 1; }
inline int gety(int y) { return lower_bound(all(ys), y) - ys.begin() + 1; }

int main() {
    vector<q1> Q1;
    vector<q2> Q2;
    int N, Q; scanf("%d%d",&N,&Q);
    for(int i=0; i<N; i++) {
        int X, Y; scanf("%d%d",&X,&Y);
        xs.push_back(X); ys.push_back(Y);
        Q1.push_back({X, Y, X+Y, 0, i});
        Q2.push_back({X, Y, 0, i});
        A[i] = {X, Y};
    }
    for(int i=0; i<Q; i++) {
        int X, Y, Z; scanf("%d%d%d",&X,&Y,&Z);
        xs.push_back(X); ys.push_back(Y);
        if(X + Y > Z) Q2.push_back({X, Y, 1, i});
        else Q1.push_back({X, Y, Z, 1, i});
    }
    sort(all(xs)); xs.resize(unique(all(xs)) - xs.begin());
    sort(all(ys)); ys.resize(unique(all(ys)) - ys.begin());
    sort(all(Q1), [&](q1 A, q1 B) {
        if(A.z == B.z) return A.ty < B.ty;
        return A.z > B.z;
    });
    sort(all(Q2), [&](q2 A, q2 B) {
        if(A.x == B.x) return A.ty < B.ty;
        return A.x > B.x;
    });
    int xsz = xs.size(), ysz = ys.size(), cnt = 0;
    fenwick XF(xsz), YF(ysz);
    for(auto& it: Q1) {
        if(it.ty == 0) {
            ++cnt;
            XF.upd(getx(it.x));
            YF.upd(gety(it.y));
        }
        if(it.ty == 1) {
            ans[it.id] = cnt - XF.get(getx(it.x) - 1) - YF.get(gety(it.y) - 1);
        }
    }
    fenwick F(ysz);
    for(auto& it: Q2) {
        if(it.ty == 0) {
            F.upd(gety(it.y));
        }
        if(it.ty == 1) {
            ans[it.id] = F.sum(gety(it.y), ysz);
        }
    }
    for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, Q; scanf("%d%d",&N,&Q);
               ~~~~~^~~~~~~~~~~~~~
examination.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int X, Y; scanf("%d%d",&X,&Y);
                   ~~~~~^~~~~~~~~~~~~~
examination.cpp:45:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int X, Y, Z; scanf("%d%d%d",&X,&Y,&Z);
                      ~~~~~^~~~~~~~~~~~~~~~~~~

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