Submission #907259

#	Time	Username	Problem	Language	Result	Execution time	Memory
907259		a_l_i_r_e_z_a	Examination (JOI19_examination)	C++17	100 / 100	903 ms	51540 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 int maxn = 1e5 + 5;
const ll inf = 1e9 + 7;
int n, q, cur, arr[maxn], ans[maxn];
pll a[maxn];
vector<ll> vec[maxn * 2], fen[maxn * 2];

struct B{
    ll A, B, Z, ind;
} b[maxn];

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

bool cmp2(B i, B j){
    return i.Z < j.Z;
}

void upd(int p, ll x, int d){
    for(; p; p /= 2){
        int j = lower_bound(all(vec[p]), x) - vec[p].begin();
        for(j++; j < fen[p].size(); j += j & -j) fen[p][j] += d;
    }
}

int get__(int i, int j){
    int res = 0;
    for(; j; j &= j - 1) res += fen[i][j];
    return res;
}

int get_(int i, ll x){
    int j = lower_bound(all(vec[i]), x) - vec[i].begin();
    return get__(i, vec[i].size()) - get__(i, j);
}

int get(int l, int r, ll x){
    int res = 0;
    for(l += n, r += n; l < r; l /= 2, r /= 2){
        if(l & 1) res += get_(l++, x);
        if(r & 1) res += get_(--r, x);
    }
    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 >> a[i].S;
        arr[i] = i;
    }
    sort(a, a + n);
    sort(arr, arr + n, cmp);
    for(int i = 0; i < n; i++){
        vec[i + n].pb(a[i].S);
        fen[i + n].resize(2);
    }
    for(int i = n - 1; i; i--){
        vec[i].resize(vec[i * 2].size() + vec[i * 2 + 1].size());
        merge(all(vec[i * 2]), all(vec[i * 2 + 1]), vec[i].begin());
        vec[i].resize(unique(all(vec[i])) - vec[i].begin());
        fen[i].resize(vec[i].size() + 1);
    }
    for(int i = 0; i < n; i++) upd(i + n, a[i].S, 1);
    for(int i = 0; i < q; i++){
        cin >> b[i].A >> b[i].B >> b[i].Z;
        b[i].ind = i;
    }
    sort(b, b + q, cmp2);
    for(int i = 0; i < q; i++){
        while(cur < n && a[arr[cur]].F + a[arr[cur]].S < b[i].Z){
            upd(arr[cur] + n, a[arr[cur]].S, -1);
            cur++;
        }
        int j = lower_bound(a, a + n, mp(b[i].A, 0ll)) - a;
        ans[b[i].ind] += get(j, n, b[i].B);
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void upd(int, ll, int)':
examination.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(j++; j < fen[p].size(); j += j & -j) fen[p][j] += d;
      |                  ~~^~~~~~~~~~~~~~~

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