Submission #1274756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274756		dhuyyyy	Examination (JOI19_examination)	C++20	100 / 100	2016 ms	923700 KiB

examination

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using aa = array<int,3>;
using ii = pair<int,int>;

const int N = 2e5+5;
const int M = 1e5+5;
const int MOD = 1e9+7;

struct Query{
    int a,b,sum,id;
} p[N];

bool cmp(Query a,Query b){
    if (a.sum == b.sum) return a.id < b.id;
    return a.sum > b.sum;
}
int n, m, q;

int res[M];

vector <int> compress;

int get_compress(int val){
    return lower_bound(compress.begin(),compress.end(),val) - compress.begin() + 1;
}
struct Tri{
    int timer = 0;
    int cnt = 0;
    vector<array<int,2>> trie;
    vector <int> num;
    void build(){
        trie.push_back({0,0});
        num.push_back(0);
    }
    void add(int val){
        int u = 0;
        cnt++;
        for (int i = 19; i >= 0; i--){
            int k = val >> i & 1;
            while (trie.size() <= u) build();
            if (!trie[u][k]) trie[u][k] = ++timer;
            u = trie[u][k];
            while (trie.size() <= u) build();
            num[u]++;
        }
    }
    int get(int val){
        int u = 0;
        int res = 0;
        for (int i = 19; i >= 0; i--){
            int k = val >> i & 1;
            while (trie.size() <= u) build();
            if (k && trie[u][0]) res += num[trie[u][0]];
            if (!trie[u][k]) return res;
            u = trie[u][k];
        }
        return res;
    }
};
struct SMT{
    int n;
    vector <Tri> t;
    SMT (int _n = 0) : n(_n){
        t.assign((n << 2),{0});
    }
    void update(int id,int l,int r,int pos,int val){
        if (r < pos || l > pos) return;
        t[id].add(val);
        if (l == r) return;
        int mid = (l + r) >> 1;
        update(id*2,l,mid,pos,val);
        update(id*2+1,mid+1,r,pos,val);
    }
    int get_cnt(int id,int l,int r,int u,int v,int val){
        if (r < u || l > v) return 0;
        if (u <= l && r <= v){
            return t[id].cnt - t[id].get(val);
        }
        int mid = (l + r) >> 1;
        int t1 = get_cnt(id*2,l,mid,u,v,val);
        int t2 = get_cnt(id*2+1,mid+1,r,u,v,val);
        return t1 + t2;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> p[i].a >> p[i].b;
        p[i].sum = p[i].a + p[i].b;
        p[i].id = i;
        compress.push_back(p[i].a);
        compress.push_back(p[i].b);
    }
    for (int i = n + 1; i <= n + q; i++){
        cin >> p[i].a >> p[i].b >> p[i].sum;
        compress.push_back(p[i].a);
        compress.push_back(p[i].b);
        p[i].id = i;
    }
    sort(compress.begin(),compress.end());
    compress.erase(unique(compress.begin(),compress.end()),compress.end());
    m = (int)compress.size();
    sort(p+1,p+1+n+q,cmp);
    for (int i = 1; i <= n + q; i++){
        p[i].a = get_compress(p[i].a);
        p[i].b = get_compress(p[i].b);
    }
    SMT Tree(m);
    for (int i = 1; i <= n + q; i++){
        if (p[i].id <= n) Tree.update(1,1,m,p[i].a,p[i].b);
        else res[p[i].id - n] = Tree.get_cnt(1,1,m,p[i].a,m,p[i].b);
    }
    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
    return 0;
}

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