제출 #1347751

#제출 시각아이디문제언어결과실행 시간메모리
1347751Born_To_LaughExamination (JOI19_examination)C++17
0 / 100
235 ms111232 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;

struct Fenwick
{
    int n;
    vector<int> bit;
    void init(int len){
        n = len;
        bit.assign(n + 1, 0);
    }
    Fenwick(int len = 0){
        init(len);
    }
    void upd(int pos, int val){
        for(; pos<=n; pos += pos & -pos) bit[pos] += val;
    }
    int qr(int pos){
        int ans = 0;
        for(; pos>0; pos -= pos & -pos) ans += bit[pos];
        return ans;
    }
    int qr(int l, int r){
        return qr(r) - qr(l - 1);
    }
};

const int maxn = 5e5 + 10;

int n, q;
int a[maxn], b[maxn];
int x[maxn], y[maxn], z[maxn];

Fenwick ft[4]; 
/*
ft1 = cnt(a >= x, b >= y)
ft2 = cnt(a + b >= z, a < x)
ft3 = cnt(a + b >= z, b < y)
*/

ll ans[maxn];

int num[maxn];//a + b

vector<int> upda[maxn][4];//update list

vector<pair<int, int>> qrspe[maxn];// ans[qr.se] += qr.fi;

vector<int> qr0[maxn];//qr[i] = qr a + b >= i
vector<pair<int, int>> qr1[maxn];//ans[qr.se] -= qr.fi;
vector<pair<int, int>> qr2[maxn];//ans[qr.se] -= qr.fi;

vector<int> temp[4];//a+b/z ; a/x ; b/y
int get_pos(int x, int id){
    return int(lower_bound(alle(temp[id]), x) - temp[id].begin());
}

void solve(){
    cin >> n >> q;
    temp[1].push_back(-INF);
    temp[2].push_back(-INF);
    temp[3].push_back(-INF);
    for(int i=1; i<=n; ++i){
        cin >> a[i] >> b[i];
        temp[1].push_back(a[i] + b[i]);
        temp[2].push_back(a[i]);
        temp[3].push_back(b[i]);
    }
    for(int i=1; i<=q; ++i){
        cin >> x[i] >> y[i] >> z[i];
        temp[1].push_back(z[i]);
        temp[2].push_back(x[i]);
        temp[3].push_back(y[i]);
        temp[1].push_back(z[i] - 1);
        temp[2].push_back(x[i] - 1);
        temp[3].push_back(y[i] - 1);
    }
    sort(alle(temp[1]));
    sort(alle(temp[2]));
    sort(alle(temp[3]));
    temp[1].erase(unique(alle(temp[1])), temp[1].end());
    temp[2].erase(unique(alle(temp[2])), temp[2].end());
    temp[3].erase(unique(alle(temp[3])), temp[3].end());
    ft[1].init(temp[1].size() + 5);
    ft[2].init(temp[2].size() + 5);
    ft[3].init(temp[3].size() + 5);
    for(int i=1; i<=n; ++i){
        num[get_pos(a[i] + b[i], 1)]++;
        upda[get_pos(a[i], 2)][1].push_back(get_pos(b[i], 3));
        upda[get_pos(a[i] + b[i], 1)][2].push_back(get_pos(a[i], 2));
        upda[get_pos(a[i] + b[i], 1)][3].push_back(get_pos(b[i], 3));
    }
    for(int i=1; i<=q; ++i){
        if(x[i] + y[i] >= z[i]){
            qrspe[get_pos(x[i], 2)].push_back({get_pos(y[i], 3), i});
        }
        else{
            qr0[get_pos(z[i], 1)].push_back(i);
            qr1[get_pos(z[i], 1)].push_back({get_pos(x[i] - 1, 2), i});
            qr2[get_pos(z[i], 1)].push_back({get_pos(y[i] - 1, 3), i});
        }
    }
    ll cnt = 0;
    for(int i=temp[1].size(); i>=1; --i){
        cnt += num[i];
        for(auto &elm: qr0[i]) ans[elm] += cnt;
    }
    for(int i=temp[2].size(); i>=1; --i){
        for(auto &elm: upda[i][1]) ft[1].upd(elm, 1);
        for(auto &elm: qrspe[i]){
            ans[elm.se] = ft[1].qr(elm.fi, ft[1].n);
        }
    }
    for(int i=temp[1].size(); i>=1; --i){
        for(auto &elm: upda[i][2]) ft[2].upd(elm, 1);
        for(auto &elm: qr1[i]){
            ans[elm.se] -= ft[2].qr(elm.fi);
        }
    }
    for(int i=temp[1].size(); i>=1; --i){
        for(auto &elm: upda[i][3]) ft[3].upd(elm, 1);
        for(auto &elm: qr2[i]){
            ans[elm.se] -= ft[3].qr(elm.fi);
        }
    }
    for(int i=1; i<=q; ++i){
        cout << ans[i] << '\n';
    }
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...