oj.uz

Submission #833042

# Submission time Handle Problem Language Result Execution time Memory
833042 2023-08-21T20:42:53 Z Farhan_HY Examination (JOI19_examination) C++14
0 / 100
 110 ms 38352 KB 
#include <bits/stdc++.h>
#define int long long
#define F first 
#define S second 
#define T int tc; cin >> tc; while(tc--) 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
using namespace std;
const int inf = 8e18;
const int N = 1e6 + 6;
const int M = 505;
const int LOG = 22;
const int CHAR = 26;
const int mod = 1e9 + 7;
const int mod2 = 998244353;
const float pi = atan(1) * 4;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const char d[] = {'R', 'L', 'U', 'D'};
int n, q;
int a[N], b[N], ans[10];
vector<int> v[N];
pair<int, int> p[N];
pair<pair<int, int>, int> qu[N];
struct segment_tree {
    vector<int> tree;
    void resize() {
        tree.clear();
        tree.resize(4 * n + n);
    }

    void update(int node, int tl, int tr, int idx) {
        if (tr == tl) {
            tree[node]++;
            return;
        }
        int mid = (tl + tr) / 2;
        if (idx <= mid)
            update(2 * node, tl, mid, idx);
        else
            update(2 * node + 1, mid + 1, tr, idx);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    void update(int idx) {
        update(1, 1, n, idx);
    }

    int get(int node, int tl, int tr, int l, int r) {
        if (l <= tl && tr <= r) return tree[node];
        if (tl > r || tr < l) return 0;
        int mid = (tl + tr) / 2;
        int p1 = get(2 * node, tl, mid, l, r);
        int p2 = get(2 * node, mid + 1, tr, l, r);
        return p1 + p2;
    }
    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
} tree;

main() {
    IOS
    cin >> n >> q;
    tree.resize();
    for(int i = 1; i <= n; i++) cin >> p[i].F >> p[i].S;
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = p[i].F;
        b[i] = p[i].S;
        v[b[i]].push_back(i);
    }
    for(int i = 1; i <= q; i++) {
        cin >> qu[i].F.S >> qu[i].F.F;
        int x;
        cin >> x;
        qu[i].S = i;
    }
    sort(qu + 1, qu + q + 1, greater<pair<pair<int, int>, int>>());
    int j = 100000;
    for(int i = 1; i <= q; i++) {
        while(j >= qu[i].F.F) {
            for(auto x: v[j]) tree.update(x);
            j--;
        }
        int x = qu[i].F.S, y = qu[i].F.F, idx = qu[i].S;
        if (a[n] < x) {
            ans[idx] = 0;
            continue;
        }
        int l = 1, r = n;
        while(l < r) {
            int mid = (l + r) / 2;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        ans[idx] = tree.get(l, n);
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Compilation message

examination.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:84:28: warning: unused variable 'y' [-Wunused-variable]
   84 |         int x = qu[i].F.S, y = qu[i].F.F, idx = qu[i].S;
      |                            ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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