Submission #1202119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202119		g4yuhg	Examination (JOI19_examination)	C++20	43 / 100	490 ms	60464 KiB

examination

#include<bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 300005
using namespace std;
struct Query {
    ll x, y, z, id;
} qr[N];
bool cmp1(Query A, Query B) {
    return A.z > B.z;
}
ll n, q, kq[N], nn;
pii a[N], b[N];
bool cmp(pii a, pii b) {
    return a.fi + a.se > b.fi + b.se;
}
vector<ll> pos[N], bit[N];
void fakeAdd(ll u, ll v, ll x) {
    while (u <= n) {
        pos[u].push_back(v);
        u += u & (-u);
    }
}
void fakeGet(ll u, ll v) {
    while (u > 0) {
        pos[u].push_back(v);
        u -= u & (-u); 
    }
}
void pre() {
    for (int i = 1; i <= n; i ++) {
        pos[i].push_back(0);
        sort(pos[i].begin(), pos[i].end());
        pos[i].resize(unique(pos[i].begin(), pos[i].end()) - pos[i].begin());
        bit[i].assign(pos[i].size(), 0);
    }
}
void update(ll u, ll v, ll x) {
    for (int i = u; i <= n; i += i & (-i)) {
        for (int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j < bit[i].size(); j += j & (-j)) {
            bit[i][j] += x;
        }
    }
}
ll get(ll u, ll v) {
    ll ans = 0;
    for (int i = u; i > 0; i -= i & (-i)) {
        for (int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j > 0; j -= j & (-j)) {
            ans += bit[i][j];
        }
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> nn >> q;
    vector<ll> nenso;
    for (int i = 1; i <= nn; i ++) {
        cin >> a[i].fi >> a[i].se;
        nenso.push_back(a[i].fi);
        nenso.push_back(a[i].se);
    }
    sort(a + 1, a + 1 + nn, cmp);
    for (int i = 1; i <= q; i ++) {
        cin >> qr[i].x >> qr[i].y >> qr[i].z;
        qr[i].id = i;
        nenso.push_back(qr[i].x);
        nenso.push_back(qr[i].y);
    }
    sort(nenso.begin(), nenso.end()); nenso.resize(unique(nenso.begin(), nenso.end()) - nenso.begin());
    n = nenso.size();
    for (int i = 1; i <= nn; i ++) {
        b[i].fi = lower_bound(nenso.begin(), nenso.end(), a[i].fi) - nenso.begin() + 1;
        b[i].se = lower_bound(nenso.begin(), nenso.end(), a[i].se) - nenso.begin() + 1;
        b[i].fi = n - b[i].fi + 1;
        b[i].se = n - b[i].se + 1;
        fakeAdd(b[i].fi, b[i].se, 1);
        //cout << a[i].fi << " " << a[i].se << endl;
    }
    for (int i = 1; i <= q; i ++) {
        qr[i].x = lower_bound(nenso.begin(), nenso.end(), qr[i].x) - nenso.begin() + 1;
        qr[i].y = lower_bound(nenso.begin(), nenso.end(), qr[i].y) - nenso.begin() + 1;
        qr[i].x = n - qr[i].x + 1;
        qr[i].y = n - qr[i].y + 1;
        fakeGet(qr[i].x, qr[i].y);
        //cout << qr[i].z << endl;
    }
    sort(qr + 1, qr + 1 + q, cmp1);
    pre();
    ll cur = 1;
    for (int i = 1; i <= q; i ++) {
        while (a[cur].fi + a[cur].se >= qr[i].z && cur <= nn) {
            update(b[cur].fi, b[cur].se, 1);
            //cout << "upd: " << a[cur].fi << " " << a[cur].se << " " << b[cur].fi << " " << b[cur].se << endl; 
            cur ++ ;
        }
        ll id = qr[i].id;
        kq[id] = get(qr[i].x, qr[i].y);
        //cout << "query: " << qr[i].x << " " << qr[i].y << " " << cur << " " << (get(n, qr[i].y) + get(qr[i].x, n) + get(qr[i].x, qr[i].y)) << endl;
    }
    for (int i = 1; i <= q; i ++) {
        cout << kq[i] << endl;
    }
    //update(70, 70,1);
    //update(35, 100, 1);
    //cout << get(20, 50);
    return 0;
}

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