oj.uz

Submission #715192

# Submission time Handle Problem Language Result Execution time Memory
715192 2023-03-26T07:42:08 Z murad_2005 Examination (JOI19_examination) C++14
20 / 100
 414 ms 22516 KB 
#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 <= 1000 && q <= 1000){
        Sub1(n, q);
    }else{
        Sub2(n, q);
    }
}

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9612 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 17 ms 10012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 22504 KB Output is correct
2 Correct 399 ms 22500 KB Output is correct
3 Correct 405 ms 22428 KB Output is correct
4 Correct 359 ms 22468 KB Output is correct
5 Correct 301 ms 22500 KB Output is correct
6 Correct 259 ms 22504 KB Output is correct
7 Correct 379 ms 22504 KB Output is correct
8 Correct 377 ms 22516 KB Output is correct
9 Correct 348 ms 22516 KB Output is correct
10 Correct 255 ms 22372 KB Output is correct
11 Correct 321 ms 22264 KB Output is correct
12 Correct 217 ms 22172 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 22504 KB Output is correct
2 Correct 399 ms 22500 KB Output is correct
3 Correct 405 ms 22428 KB Output is correct
4 Correct 359 ms 22468 KB Output is correct
5 Correct 301 ms 22500 KB Output is correct
6 Correct 259 ms 22504 KB Output is correct
7 Correct 379 ms 22504 KB Output is correct
8 Correct 377 ms 22516 KB Output is correct
9 Correct 348 ms 22516 KB Output is correct
10 Correct 255 ms 22372 KB Output is correct
11 Correct 321 ms 22264 KB Output is correct
12 Correct 217 ms 22172 KB Output is correct
13 Incorrect 401 ms 22500 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9612 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 17 ms 10012 KB Output isn't correct
8 Halted 0 ms 0 KB -