Submission #830529

#	Time	Username	Problem	Language	Result	Execution time	Memory
830529		Shreyan_Paliwal	Examination (JOI19_examination)	C++17	0 / 100	1207 ms	22928 KiB

examination

// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

template<typename T>
string tostr(const T& value) {
    ostringstream oss;
    oss << value;
    return oss.str();
}

template<typename... Args>
string fstr(const string& format, Args... args) {
    string result = format;
    size_t pos = 0;
    size_t argIndex = 0;

    auto replaceArg = [&](const auto& arg) {
        pos = result.find("{}", pos);
        if (pos != string::npos) {
            result.replace(pos, 2, tostr(arg));
            ++argIndex;
        }
    };

    (replaceArg(args), ...);

    return result;
}

/*
 * Keeps mint objects modulo MOD constant
*/

// const int MOD = 1e9 + 7;
// struct mint {
//     int x;

//     mint() { x = 0; }
//     mint(int X) { x = X; }
//     mint(long long X) { x = ((X % MOD) + MOD) % MOD; }
//     mint(unsigned long long X) { x = (X % MOD); }

//     mint pow(int k) { mint r = 1, a = *this; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }

//     mint& operator+=(mint o) { if ((x += o.x) >= MOD) x -= MOD; return *this; }
//     mint& operator-=(mint o) { if ((x += MOD - o.x) >= MOD) x -= MOD; return *this; }
//     mint& operator*=(mint o) { x = 1ll * x * o.x % MOD; return *this; }
//     mint& operator/=(mint o) { return (*this) *= o.pow(MOD - 2); }

//     mint operator+(mint o) const { return mint(*this) += o; }
//     mint operator-(mint o) const { return mint(*this) -= o; }
//     mint operator*(mint o) const { return mint(*this) *= o; }
//     mint operator/(mint o) const { return mint(*this) /= o; }

//     bool operator<(mint o) const { return x < o.x; }

//     friend ostream& operator<<(ostream& os, mint a) { os << a.x; return os; }
// };

/*
 * Matrices
 * Multiplication
*/

// typedef vector<vector<int>> MAT;
// struct Matrix {
//     MAT v;
//     Matrix(MAT V) { swap(v, V); }
//     Matrix(int a, int b) { v.resize(a, vector<int>(b, 0)); }
//     Matrix operator*(const Matrix& o) {
//         // assert(v[0].size() == o.v.size());
//         Matrix M(v.size(), o.v[0].size());
//         for (int i = 0; i < v.size(); i++)
//             for (int j = 0; j < o.v[0].size(); j++)
//                 for (int k = 0; k < (int)v[0].size(); k++)
//                     M.v[i][j] += v[i][k] * o.v[k][j];
//         return M;
//     }
//     Matrix operator^(int k) {
//         if (k&1) return (((*this)*(*this))^(k/2))*(*this);
//         else return ((*this)*(*this))^(k/2);
//     }
// };

/*
 * Segment Tree
 * - RANGE QUERY
 * - RANGE UPDATE
*/

// template<class T>
// T identity; // [SET IDENTITY OF CLASS T, hardcode T classname]
// struct ND {
//     ND* ch[2] = { nullptr, nullptr };
//     T v, f;

//     inline void create() {
//         if (!ch[0]) ch[0] = new ND; // [POTENTIALLY UPDATE VALUES]
//         if (!ch[1]) ch[1] = new ND; // [POTENTIALLY UPDATE VALUES]
//     }

//     inline T merge(int l, int r) {
//         // [INSERT CODE FOR MERGE SEGMENT]
//     }

//     inline void push(int l, int r) {
//         create();
//         // [INSERT CODE FOR PUSHING SEGMENT FLAG]
//     }

//     void upd(int l, int r, int L, int R, T K) {
//         push(l, r);
//         if (R < l || r < L) return;
//         if (L <= l && r <= R) {
//             // [INSERT CODE FOR UPDATE SEGMENT]
//             return;
//         }
//         int m = (l + r) >> 1;
//         ch[0]->upd(l, m, L, R, K);
//         ch[1]->upd(m+1, r, L, R, K);
//         merge(l, r);
//     }

//     T qry(int l, int r, int L, int R) {
//         push(l, r);
//         if (R < l || r < L) return identity;
//         if (L <= l && r <= R) return v;
//         int m = (l + r) >> 1;
//         return OPERATION(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R));
//     }

//     ~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; }
// };

/*
 * Convex Hull Trick
 * - ORDERED SLOPES
 * - UNORDERED QUERIES O(N log N), ORDERED QUERIES O(N)
*/

// struct F {
//     int a, b;
//     F() {}
//     F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; }
//     bool operator<(F o) const { return a*o.b < b*o.a; }
//     bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
//     int m, b;
//     int operator()(int x) { return m*x + b; }
//     F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// struct CHT {
//     vector<L> h;
//     // deque<L> h; // if using SECOND CODE in QRY FUNCTION
//     void add(L l) {
//         // // min hull + decreasing slopes OR max hull + increasing slopes
//         // while (h.size() >= 2 && (h.end()[-2]^l) <= (h.end()[-2]^h.back())) h.pop_back();
//         // h.push_back(l);

//         // // min hull + increasing slopes OR max hull + decreasing slopes
//         // while (h.size() >= 2 && (h.end()[-2]^h.back()) <= (h.end()[-2]^l)) h.pop_back();
//         // h.push_back(l);
//     }
//     int qry(int x) {
//         // O(N log N) time, unordered queries
//         // int lo = 0, hi = h.size()-1;
//         // while (lo < hi) {
//         //     int m = (lo + hi) >> 1;
//         //     if (h[m](x) < h[m+1](x)) // < or > depending on min/max qry
//         //         lo = m+1;
//         //     else 
//         //         hi = m;
//         // }
//         // return h[lo](x);

//         // if need O(N) time, use **DEQUE INSTEAD OF VECTOR** & use code below
//         // while (h.size() >= 2 && h[1](x) < h[0](x)) h.pop_front(); // < or > depending on min/max qry
//         // return h[0](x);
//     }
// };

/*
 * Li Chao Tree 
 * UNORDERED SLOPES, UNORDERED QUERIES O(N log N)
 * Extension of segment tree
*/

// struct F {
//     int a, b;
//     F() {}
//     F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; }
//     bool operator<(F o) const { return a*o.b < b*o.a; }
//     bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
//     int m, b;
//     int operator()(int x) { return m*x + b; }
//     F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// // #define OP(a, b) (a < b) // DEFINE OPERATOR
// // #define OPR(a, b) (min(a,b)) // DEFINE OPERATOR
// #define OP(a, b) (a > b)
// #define OPR(a, b) (max(a,b))
// struct ND {
//     ND * ch[2] = { nullptr, nullptr };
//     L v = L{1, 0};
//     void create() {
//         if (!ch[0]) { ch[0] = new ND; ch[0]->v = v; }
//         if (!ch[1]) { ch[1] = new ND; ch[1]->v = v; }
//     }
//     void upd(int l, int r, L V) {
//         // update the li chao tree with line V
//         if (v.m == V.m && v.b == V.b) return;
//         if (l == r) {
//             // if new line is better, swap
//             if (OP(V(l), v(l))) swap(V, v);
//             return;
//         }
//         create();
//         int m = (l + r) >> 1; // midpoint
//         if (OP(V(m), v(m))) swap(V, v); // if new line is better at mid, it has one half, so swap
//         F x = v ^ V; // intersection of two lines
//         if (x <= F(m, 1)) 
//             ch[0]->upd(l, m, V);
//         else
//             ch[1]->upd(m+1, r, V);
//     }
//     int qry(int l, int r, int X) {
//         // qry li chao tree for x coord X        
//         int ret = v(X); // gets value for current segment
//         if (l != r) {
//             int m = (l + r) >> 1;
//             if (X <= m && ch[0] != nullptr) return OPR(ret, ch[0]->qry(l, m, X));
//             if (X > m && ch[1] != nullptr) return OPR(ret, ch[1]->qry(m+1, r, X));
//         }
//         return ret;
//     }
// };
// #undef OP
// #undef OPR

// /*
//  * Persistant Array 
//  * 
//  * Update @ time & index from time' - Will create update of time T' to time T while keeping T intact
//  * Query time & index - log N
//  * 
//  * Time complexity - O(N + K log N) where K is number of updates + queries
//  * Memory complexity - O(N + K log N) where K is the number of updates
// */
// struct Node {
//     int v;
//     Node *l, *r;
//     Node(int x) : v(x), l(nullptr), r(nullptr) {}
//     Node(Node* L, Node* R) : v(0), l(L), r(R) {}
// };
// struct PersArray {
//     int* init_array;
//     int n;
//     Node* roots[MAX_TIME];
//     Node* build(int l, int r) {
//         if (l == r) { return new Node(init_array[l]); }
//         int m = (l + r) >> 1;
//         return new Node(build(l, m), build(m+1, r));
//     }
//     void init() { roots[0] = build(0, n-1); }
//     Node* UPD(Node* nd, int K, int V, int l, int r) {
//         if (l == r) { return new Node(V); }
//         int m = (l + r) >> 1;
//         if (K <= m) return new Node(UPD(nd->l, K, V, l, m), nd->r);
//         else return new Node(nd->l, UPD(nd->r, K, V, m+1, r));
//     }
//     int QRY(Node* nd, int K, int l, int r) {
//         if (l == r) return nd->v;
//         int m = (l + r) >> 1;
//         if (K <= m) return QRY(nd->l, K, l, m);
//         else return QRY(nd->r, K, m+1, r);
//         return 0;
//     }
//     int qry(int K, int T) {
//         return QRY(roots[T], K, 0, n-1);
//     }
//     void upd(int K, int V, int T, int Tp) {
//         roots[T] = UPD(roots[Tp], K, V, 0, n-1);
//     }
// };

// /*
//  * Heavy Light Decomposition, HLD
//  *
//  * Query paths on tree
//  * Qry - (log N)^2
//  * Upd - (log N)^2
//  * 
//  * Place segment trees on nodes
// */
// template<int SZ> struct HLD {
//     int n;
//     int sz[SZ], dpth[SZ], par[SZ], 
//         root[SZ], id[SZ], cur=0;
//     // ND* st; // IMPLEMENT SEGMENT TREE
//     void dfs(int nd, int p) {
//         par[nd] = p;
//         dpth[nd] = dpth[p] + 1;
//         sz[nd] = 1;
//         for (auto i : adj[nd])
//             if (i != p) {
//                 dfs(i, nd);
//                 sz[nd] += sz[i];
//             }
//     }
//     void dfs_hld(int nd, int par, int top) {
//         root[nd] = top;
//         id[nd] = cur++;
//         // POTENTIALLY UPDATE segment tree at id[nd] to value of nd
//         int hch = -1, hb = -1;
//         for (auto i : adj[nd])
//             if (i != par && (hch == -1 || hb < sz[i]))
//                 hb = sz[i], hch = i;
//         if (hch == -1) return;
//         dfs_hld(hch, nd, top);
//         for (auto i : adj[nd])
//             if (i != par && i != hch)
//                 dfs_hld(i, nd, i);
//     }
//     void init(int N) {
//         n = N;
//         dpth[0] = 0; 
//         dfs(0, 0);
//         dfs_hld(0, 0, 0);
//     }
//     int lca(int a, int b) {
//         while (root[a] != root[b]) {
//             if (dpth[root[a]] < dpth[root[b]]) swap(a, b);
//             a = par[root[a]];
//         }
//         return dpth[a] < dpth[b] ? a : b;
//     }
//     int qry(int a, int b) {
//         // first one is always higher depth, aka lower in tree
//         int ret = 0; // SET SOME IDENTITY
//         while (root[a] != root[b]) {
//             if (dpth[root[a]] < dpth[root[b]]) swap(a, b);
//             // ret = QRY // UPD ret with QRY from a --> root[a]
//             a = par[root[a]];
//         }
//         if (dpth[a] < dpth[b]) swap(a, b);
//         // ret = QRY // UPD ret with QRY from a --> b
//         return ret;
//     }
// };

/*
 * Binary Indexed Tree
*/
template<int SZ> struct BIT {
    int bit[SZ+1], n;
    void init(int N) { n = N; memset(bit, 0, sizeof(n) * (N+1)); }
    void upd(int k, int v=1) { for (; k <= n; k += (k & -k)) bit[k] += v; }
    int qry(int k) { int r = 0; for (; k; k -= (k & -k)) r += bit[k]; return r; }
};


#define int long long

const int maxn = 100005;
const int blcksz = 320;
const int INF = 2e18;

int n, q;
int a[maxn], b[maxn], c[maxn];
int x[maxn], y[maxn], z[maxn];
int s[maxn], s2[maxn], s3[maxn];
int invs[maxn];

int blck_min_a[blcksz];

unordered_map<int,int> m;

BIT<maxn> bit;

void condense() {
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(a[i]);
        s.insert(b[i]);
        s.insert(c[i]);
    }
    int cnt = 0;
    for (auto i : s) m[i] = cnt++;
}

void solve() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i]; 
        c[i] = a[i] + b[i];
    }
    for (int i = 0; i < q; i++)
        cin >> x[i] >> y[i] >> z[i];

    bit.init(n);

    iota(s, s+n, 0);
    iota(s2, s2+n, 0);
    iota(s3, s3+q, 0);

    condense();


    sort(s, s+n, [&](int i, int j){ return a[i] > a[j]; });
    sort(s, s+n, [&](int i, int j){
        if ((i / blcksz) == (j / blcksz))
            return b[i] > b[j];
        return a[i] > a[j];
    });
    for (int i = 0; i < n; i++) invs[s[i]] = i;

    // for (int i = 0; i < n; i++)
    //     cout << a[s[i]] << ' ' << b[s[i]] << ' ' << c[s[i]] << endl;

    // cout << "------" << endl;

    sort(s2, s2+n, [&](int i, int j){
        return c[i] > c[j];
    });

    sort(s3, s3+n, [&](int i, int j){
        return z[i] > z[j];
    });

    for (int i = 0; i*blcksz < n; i++) {
        blck_min_a[i] = INT_MAX;
        for (int j = i*blcksz; j < (i+1)*blcksz && j<n; j++)
            blck_min_a[i] = min(blck_min_a[i], a[s[j]]);
    }

    for (int i = 0, j = 0; i < q; i++) {
        // cout << "____" << endl;
        while (j < n && c[s2[j]] >= z[i])
            bit.upd(invs[s2[j++]] + 1);
        
        int ans = 0;
        for (int k = 0; k * blcksz < n; k++) {
            // if end of block is still greater for the a, just upperbound on b
            if (blck_min_a[k] >= x[i]) {
                int lo = k * blcksz, hi = min(n-1, (k+1)*blcksz-1);
                while (lo < hi) {
                    int m = (lo + hi + 1) >> 1;
                    // cout << b[s[m]] << ' ' << y[i] << endl;
                    if (b[s[m]] >= y[i])
                        lo = m;
                    else 
                        hi = m-1;
                }
                // cout << lo << ' ' << bit.qry(lo+1) << ' ' << k*blcksz << ' ' << bit.qry(k*blcksz) << endl;
                ans += bit.qry(lo + 1) - bit.qry(k*blcksz); // k*blcksz-1 + 1 cancel out 
            } else {
                // else just go one by one
                for (int kp = k*blcksz; kp < (k+1)*blcksz && kp < n; kp++)
                    ans += a[s[kp]] >= x[i] &&  
                           b[s[kp]] >= y[i] &&  
                           c[s[kp]] >= z[i];
                
                break;
            }
        }

        cout << ans << endl;
    }
}

// #define LOCAL
// #define CODEFORCES
signed main() {
    #ifndef LOCAL
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    #endif
    #ifdef LOCAL
    freopen("main.in", "r", stdin);
    #endif
    int t; 
    #ifdef CODEFORCES
    cin >> t;
    #endif
    #ifndef CODEFORCES
    t=1;
    #endif
    while(t--) solve();
    return 0;
}

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