Submission #306683

#	Time	Username	Problem	Language	Result	Execution time	Memory
306683		jainbot27	Examination (JOI19_examination)	C++17	2 / 100	3095 ms	43636 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
constexpr int blksz = 400;
typedef int node;
struct BIT{
    //ask for queries 0 idxed or remove ++idx/++r
    vector<node> bit;
    int n;
    void init(int x){
        n=x+1;
        bit.assign(n + 1,0);
    }
    node sum(int r){
        node ret = 0;
        for(r++; r ; r -= r & -r){
            ret += bit[r];
        }
        return ret;
    }
    node sum(int l, int r){
        return sum(r) - sum(l-1);
    }
    void add(int idx, node delta){
        for(idx++; idx < n; idx += idx & -idx){
            bit[idx] += delta;
        }
    }
};
struct T{
    int a, b, c, blk, q;
    bool operator<(const T& x) const{
        return blk == x.blk ? a < x.a : blk < x.blk;
    };
};
int n, q, aptr = -1, bptr = -1; vector<int> amt, ans, vals; vector<T> Q; vector<T> proc; set<int> A, B, C;
vector<vector<int>> as, bs; BIT bit; vector<int> chk;
map<int, int> compress(set<int> x){
    map<int, int> res;
    int ctr = 0;
    trav(y, x){
        res[y] = ctr;
        ctr++;
    }
    return res;
}
void upd(int pos, int dif, vector<vector<int>>&cur){
    trav(x, cur[pos]){
        int old = vals[x];
        vals[x]+=dif;
        if(old == 1 && vals[x] == 2) bit.add(x, 1);
        else if(old == 2 && vals[x] == 1) bit.add(x, -1);
    }
}
void mo(int& ptr, int x, vector<vector<int>>& cur){
    while(ptr > x){
        ptr--;
        upd(ptr, 1, cur);
    } 
    while(ptr < x){
        upd(ptr, -1, cur);
        ptr++;
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    aptr = n+q; bptr = n+q; 
    proc.resize(n);
    as.resize(n+q); bs.resize(n+q);
    bit.init(n+q);
    F0R(i, n){
        cin >> proc[i].a >> proc[i].b; proc[i].c = proc[i].b + proc[i].a;
        A.insert(proc[i].a);
        B.insert(proc[i].b);
        C.insert(proc[i].c);
    }
    Q.resize(q);
    vals.resize(q+n);
    F0R(i, q){
        cin >> Q[i].a >> Q[i].b >> Q[i].c;
        A.insert(Q[i].a);
        B.insert(Q[i].b);
        C.insert(Q[i].c);
    }
    map<int, int> acom = compress(A);
    map<int, int> bcom = compress(B);
    map<int, int> ccom = compress(C);
    F0R(i, n){
        proc[i].a = acom[proc[i].a];
        proc[i].b = bcom[proc[i].b];
        proc[i].c = ccom[proc[i].c];
    }
    sort(all(proc), [](T ax, T bx){
        return ax.c < bx.c;
    });
    chk.resize(n+q, n+q-1);
    F0R(i, n){
        as[proc[i].a].pb(i);
        bs[proc[i].b].pb(i);
        ckmin(chk[proc[i].c], i);
    }
    R0F(i, n+q-1){
        ckmin(chk[i], chk[i+1]);
    }
    F0R(i, q){
        Q[i].a = acom[Q[i].a];
        Q[i].b = bcom[Q[i].b];
        Q[i].c = ccom[Q[i].c];
        Q[i].blk = Q[i].b/blksz;
        Q[i].q = i;
    }
    sort(all(Q));
    ans.resize(q);
    F0R(i, q){
        T& cur = Q[i];
        mo(bptr, cur.b, bs);
        mo(aptr, cur.a, as);
        ans[cur.q] = bit.sum(chk[cur.c], n+q-1);
    }
    F0R(i, q){
        cout << ans[i] << "\n";
    }

    return 0;
}

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