Submission #906627

#	Time	Username	Problem	Language	Result	Execution time	Memory
906627		a_l_i_r_e_z_a	Examination (JOI19_examination)	C++17	100 / 100	1310 ms	15700 KiB

examination

// In the name of God

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 1e5 + 5;
const ll inf = 1e9 + 7;
ll n, q, cur, sq = 400, arr[maxn], ans[maxn];
pll a[maxn];
pair<pll, pll> b[maxn];
vector<ll> vec[maxn];

bool cmp(int i, int j){
    return a[i].F + a[i].S < a[j].F + a[j].S;
}

void del(int i){
    ll x = a[i].S;
    i = i / sq;
    vec[i].erase(find(all(vec[i]), x));
}

ll get(ll i, ll x){
    ll res = 0;
    for(; i < n; i += sq){
        int d = lower_bound(all(vec[i / sq]), x) - vec[i / sq].begin();
        res += vec[i / sq].size() - d;
    }
    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i].F;
        cin >> a[i].S;
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++){
        vec[i / sq].pb(a[i].S);
    }
    for(int i = 0; i < sq; i++) sort(all(vec[i]));
    for(int i = 0; i < q; i++){
        cin >> b[i].S.F >> b[i].S.S >> b[i].F.F;
        b[i].F.S = i;
    }
    sort(b, b + q);
    for(int i = 0; i < n; i++) arr[i] = i;
    sort(arr, arr + n, cmp);
    for(int i = 0; i < q; i++){
        ll Z = b[i].F.F, ind = b[i].F.S, A = b[i].S.F, B = b[i].S.S;
        while(cur < n && a[arr[cur]].F + a[arr[cur]].S < Z) del(arr[cur++]);
        int j = lower_bound(a, a + n, mp(A, 0ll)) - a;
        j = (j / sq) * sq;
        for(int k = j; ((1ll * k) < n) && ((1ll * k / sq) == (1ll * j / sq)); k++){
            if(a[k].F >= A && a[k].S >= B && a[k].F + a[k].S >= Z) ans[ind]++;
        }
        j += sq;
        if(j < n) ans[ind] += get(j, B);
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';

    return 0;
}

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