Submission #736830

#	Time	Username	Problem	Language	Result	Execution time	Memory
736830		sandry24	Examination (JOI19_examination)	C++17	100 / 100	227 ms	14028 KiB

examination

#include <bits/stdc++.h>
//#include "secret.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

int maxsz = 400005;

struct query {
    int a;
    int b;
    int sum;
    int ind;
};

struct BIT{
    int n;
    vi bit;

    BIT(int n_now){
        n = n_now;
        bit = vi(n_now+1);
    }

    void add(int x, int delta){
        for(; x <= n; x += x & -x)
            bit[x] += delta;
    }

    int get(int x){
        int sum = 0;
        for(; x > 0; x -= x & -x)
            sum += bit[x];
        return sum;
    }

    int get(int l, int r){
        return get(r) - get(l-1);
    }
};

bool cmp(query a, query b){
    if(a.sum != b.sum)
        return a.sum > b.sum;
    return a.ind < b.ind;
}
 
void solve(){
    int n, q;
    cin >> n >> q;
    vector<query> queries;
    vi ans(q);
    vi vals;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        vals.pb(a);
        vals.pb(b);
        queries.pb({a, b, a+b, -1});
    }
    for(int i = 0; i < q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        vals.pb(a);
        vals.pb(b);
        queries.pb({a, b, max(a+b, c), i});
    }
    sort(vals.begin(), vals.end());

    auto compress = [&](int a){
        return lower_bound(vals.begin(), vals.end(), a) - vals.begin() + 1;
    };

    int people = 0;
    BIT a(maxsz), b(maxsz);
    sort(queries.begin(), queries.end(), cmp);
    for(auto x : queries){
        if(x.ind == -1){
            a.add(compress(x.a), 1);
            b.add(compress(x.b), 1);
            people++;
        } else {
            ans[x.ind] = a.get(compress(x.a), maxsz) + b.get(compress(x.b), maxsz) - people;
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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