Submission #715193

#	Time	Username	Problem	Language	Result	Execution time	Memory
715193		murad_2005	Examination (JOI19_examination)	C++14	22 / 100	416 ms	22600 KiB

examination

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii pair<int, pii>
#define pllll pair<ll, ll>
#define plli pair<ll, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define size(v) v.size()
#define INF 1e9
#define f first
#define s second
#define ln "\n"

using namespace std;

vector<pii>p;

void Sub1(int n, int q){
    p.resize(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> p[i].f >> p[i].s;
    }
    while(q--){
        int x, y, z;
        cin >> x >> y >> z;
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            if(p[i].f >= x && p[i].s >= y && p[i].f + p[i].s >= z){
                cnt++;
            }
        }
        cout << cnt << "\n";
    }
}

const int up = 1e5 + 5;

vector<int>st[up << 2];

void build(int v, int l, int r){
    if(l == r){
        st[v].pb(p[l - 1].s);
    }else{
        int mid = (l + r) >> 1;
        build(v << 1, l, mid);
        build((v << 1) | 1, mid + 1, r);
        st[v].resize(r - l + 1);
        merge(all(st[v << 1]), all(st[(v << 1) | 1]), st[v].begin());
    }
}

int query(int v, int l, int r, int ql, int qr, int val){
    if(r < ql || qr < l) return 0;
    else if(ql <= l && r <= qr){
        int pos = lower_bound(all(st[v]), val) - st[v].begin();
        return size(st[v]) - pos;
    }else{
        int mid = (l + r) >> 1;
        return query(v << 1, l, mid, ql, qr, val) + query((v << 1) | 1, mid + 1, r, ql, qr, val);
    }
}

void Sub2(int n, int q){
    p.resize(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i].f >> p[i].s;
    }
    sort(all(p));
    build(1, 1, n);
    while(q--){
        int x, y, z;
        cin >> x >> y >> z;
        pii P = {x, 0};
        int pos = lower_bound(all(p), P) - p.begin();
        if(pos < n){
            cout << query(1, 1, n, pos + 1, n, y) << "\n";
        }else{
            cout << "0\n";
        }
    }
}

void solve(){
    int n, q;
    cin >> n >> q;
    if(n <= 3000 && q <= 3000){
        Sub1(n, q);
    }else{
        Sub2(n, q);
    }
}

int main(){
    int t;
    t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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