oj.uz

Submission #833045

# Submission time Handle Problem Language Result Execution time Memory
833045 2023-08-21T20:51:32 Z Farhan_HY Examination (JOI19_examination) C++14
20 / 100
 112 ms 39580 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[N];
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 + 1, 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 13 ms 23764 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 108 ms 36632 KB Output is correct
2 Correct 107 ms 39196 KB Output is correct
3 Correct 107 ms 39116 KB Output is correct
4 Correct 98 ms 37596 KB Output is correct
5 Correct 86 ms 38404 KB Output is correct
6 Correct 70 ms 36940 KB Output is correct
7 Correct 103 ms 39040 KB Output is correct
8 Correct 107 ms 39116 KB Output is correct
9 Correct 108 ms 38944 KB Output is correct
10 Correct 70 ms 38220 KB Output is correct
11 Correct 77 ms 36988 KB Output is correct
12 Correct 58 ms 36040 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 36632 KB Output is correct
2 Correct 107 ms 39196 KB Output is correct
3 Correct 107 ms 39116 KB Output is correct
4 Correct 98 ms 37596 KB Output is correct
5 Correct 86 ms 38404 KB Output is correct
6 Correct 70 ms 36940 KB Output is correct
7 Correct 103 ms 39040 KB Output is correct
8 Correct 107 ms 39116 KB Output is correct
9 Correct 108 ms 38944 KB Output is correct
10 Correct 70 ms 38220 KB Output is correct
11 Correct 77 ms 36988 KB Output is correct
12 Correct 58 ms 36040 KB Output is correct
13 Incorrect 112 ms 39580 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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