oj.uz

Submission #715190

# Submission time Handle Problem Language Result Execution time Memory
715190 2023-03-26T07:40:59 Z murad_2005 Examination (JOI19_examination) C++14
20 / 100
 507 ms 23972 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;
    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 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 23972 KB Output is correct
2 Correct 415 ms 22448 KB Output is correct
3 Correct 479 ms 22568 KB Output is correct
4 Correct 402 ms 22412 KB Output is correct
5 Correct 316 ms 22472 KB Output is correct
6 Correct 268 ms 22480 KB Output is correct
7 Correct 431 ms 22528 KB Output is correct
8 Correct 388 ms 22480 KB Output is correct
9 Correct 372 ms 22708 KB Output is correct
10 Correct 267 ms 22272 KB Output is correct
11 Correct 328 ms 22372 KB Output is correct
12 Correct 244 ms 22128 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 23972 KB Output is correct
2 Correct 415 ms 22448 KB Output is correct
3 Correct 479 ms 22568 KB Output is correct
4 Correct 402 ms 22412 KB Output is correct
5 Correct 316 ms 22472 KB Output is correct
6 Correct 268 ms 22480 KB Output is correct
7 Correct 431 ms 22528 KB Output is correct
8 Correct 388 ms 22480 KB Output is correct
9 Correct 372 ms 22708 KB Output is correct
10 Correct 267 ms 22272 KB Output is correct
11 Correct 328 ms 22372 KB Output is correct
12 Correct 244 ms 22128 KB Output is correct
13 Incorrect 507 ms 22460 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -