oj.uz

Submission #808860

# Submission time Handle Problem Language Result Execution time Memory
808860 2023-08-05T11:56:33 Z LucaIlie Examination (JOI19_examination) C++17
2 / 100
 3000 ms 242572 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<
        pair<int, int>,
        null_type,
        less<pair<int, int>>,
        rb_tree_tag,
        tree_order_statistics_node_update> ordered_set;


struct query {
    int a, b, c;
};

const int MAX_N = 1e5;
const int MAX_Q = 1e5;
const int MAX_VAL = 2e9;
int s[MAX_N], t[MAX_N], a[MAX_Q], b[MAX_Q], c[MAX_Q], ans[MAX_Q];
map<int, vector<int>> updates, queries;
vector<int> vals;

struct node {
    node *left, *right;
    ordered_set bau;
};

struct SEG_TREE {
    node *createNode() {
        node *t = new node;
        t->left = t->right = NULL;
        return t;
    }

    void update( node *v, int l, int r, int pos, int val, int i ) {
        if ( l > pos || r < pos )
            return;

        v->bau.insert( { val, i } );

        if ( l == r )
            return;

        int mid = (r - l) / 2 + l;
        if ( v->left == NULL )
            v->left = createNode();
        if ( v->right == NULL )
            v->right = createNode();
        update( v->left, l, mid, pos, val, i );
        update( v->right, mid + 1, r, pos, val, i );
    }

    int query( node *v, int l, int r, int lq, int rq, int val ) {
        if ( l > rq || r < lq )
            return 0;

        if ( lq <= l && r <= rq )
            return v->bau.size() - v->bau.order_of_key( { val, 0 } );

        int mid = (r - l) / 2 + l;
        if ( v->left == NULL )
            v->left = createNode();
        if ( v->right == NULL )
            v->right = createNode();
        return query( v->left, l, mid, lq, rq, val ) + query( v->right, mid + 1, r, lq, rq, val );
    }
};

SEG_TREE bambam;

signed main() {
    int n, q;

    cin >> n >> q;
    for ( int i = 0; i < n; i++ )
        cin >> s[i] >> t[i];
    for ( int i = 0; i < q; i++ )
        cin >> a[i] >> b[i] >> c[i];

    for ( int i = 0; i < n; i++ )
        updates[s[i] + t[i]].push_back( i ), vals.push_back( s[i] + t[i] );
    for ( int i = 0; i < q; i++ )
        queries[c[i]].push_back( i ), vals.push_back( c[i] );
    sort( vals.begin(), vals.end() );
    vals.resize( unique( vals.begin(), vals.end() ) - vals.begin() );
    reverse( vals.begin(), vals.end() );

    node *root = bambam.createNode();
    for ( int x: vals ) {
        for ( int i: updates[x] )
            bambam.update( root, 0, MAX_VAL, s[i], t[i], i );
        for ( int i: queries[x] )
            ans[i] = bambam.query( root, 0, MAX_VAL, a[i], MAX_VAL, b[i] );
    }

    for ( int i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 43 ms 33020 KB Output is correct
8 Correct 40 ms 33044 KB Output is correct
9 Correct 38 ms 33052 KB Output is correct
10 Correct 38 ms 33040 KB Output is correct
11 Correct 25 ms 7488 KB Output is correct
12 Correct 21 ms 6384 KB Output is correct
13 Correct 36 ms 32508 KB Output is correct
14 Correct 36 ms 32412 KB Output is correct
15 Correct 35 ms 32456 KB Output is correct
16 Correct 20 ms 7012 KB Output is correct
17 Correct 39 ms 33076 KB Output is correct
18 Correct 60 ms 6452 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2185 ms 242556 KB Output is correct
2 Correct 2217 ms 242572 KB Output is correct
3 Correct 2193 ms 242536 KB Output is correct
4 Correct 1490 ms 240664 KB Output is correct
5 Correct 1109 ms 216632 KB Output is correct
6 Correct 1032 ms 205256 KB Output is correct
7 Correct 1934 ms 241608 KB Output is correct
8 Correct 2043 ms 242520 KB Output is correct
9 Correct 1732 ms 241596 KB Output is correct
10 Correct 994 ms 216480 KB Output is correct
11 Correct 1316 ms 240456 KB Output is correct
12 Execution timed out 3087 ms 130572 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2185 ms 242556 KB Output is correct
2 Correct 2217 ms 242572 KB Output is correct
3 Correct 2193 ms 242536 KB Output is correct
4 Correct 1490 ms 240664 KB Output is correct
5 Correct 1109 ms 216632 KB Output is correct
6 Correct 1032 ms 205256 KB Output is correct
7 Correct 1934 ms 241608 KB Output is correct
8 Correct 2043 ms 242520 KB Output is correct
9 Correct 1732 ms 241596 KB Output is correct
10 Correct 994 ms 216480 KB Output is correct
11 Correct 1316 ms 240456 KB Output is correct
12 Execution timed out 3087 ms 130572 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 43 ms 33020 KB Output is correct
8 Correct 40 ms 33044 KB Output is correct
9 Correct 38 ms 33052 KB Output is correct
10 Correct 38 ms 33040 KB Output is correct
11 Correct 25 ms 7488 KB Output is correct
12 Correct 21 ms 6384 KB Output is correct
13 Correct 36 ms 32508 KB Output is correct
14 Correct 36 ms 32412 KB Output is correct
15 Correct 35 ms 32456 KB Output is correct
16 Correct 20 ms 7012 KB Output is correct
17 Correct 39 ms 33076 KB Output is correct
18 Correct 60 ms 6452 KB Output is correct
19 Correct 2185 ms 242556 KB Output is correct
20 Correct 2217 ms 242572 KB Output is correct
21 Correct 2193 ms 242536 KB Output is correct
22 Correct 1490 ms 240664 KB Output is correct
23 Correct 1109 ms 216632 KB Output is correct
24 Correct 1032 ms 205256 KB Output is correct
25 Correct 1934 ms 241608 KB Output is correct
26 Correct 2043 ms 242520 KB Output is correct
27 Correct 1732 ms 241596 KB Output is correct
28 Correct 994 ms 216480 KB Output is correct
29 Correct 1316 ms 240456 KB Output is correct
30 Execution timed out 3087 ms 130572 KB Time limit exceeded
31 Halted 0 ms 0 KB -