oj.uz

Submission #808848

# Submission time Handle Problem Language Result Execution time Memory
808848 2023-08-05T11:48:18 Z LucaIlie Examination (JOI19_examination) C++17
41 / 100
 2173 ms 223256 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 = 2e5;
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 SEG_TREE {
    ordered_set segTree[4 * MAX_VAL];

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

        segTree[v].insert( { val, i } );

        if ( l == r )
            return;

        int mid = (r - l) / 2 + l;
        update( v * 2 + 1, l, mid, pos, val, i );
        update( v * 2 + 2, mid + 1, r, pos, val, i );
    }

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

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

        int mid = (r - l) / 2 + l;
        return query( v * 2 + 1, l, mid, lq, rq, val ) + query( v * 2 + 2, 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() );

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

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

    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75468 KB Output is correct
2 Correct 46 ms 75464 KB Output is correct
3 Correct 50 ms 75408 KB Output is correct
4 Incorrect 52 ms 75528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 210344 KB Output is correct
2 Correct 2087 ms 212852 KB Output is correct
3 Correct 2122 ms 212876 KB Output is correct
4 Correct 1481 ms 210284 KB Output is correct
5 Correct 1310 ms 210936 KB Output is correct
6 Correct 1092 ms 198776 KB Output is correct
7 Correct 1997 ms 212752 KB Output is correct
8 Correct 1966 ms 212700 KB Output is correct
9 Correct 1764 ms 212608 KB Output is correct
10 Correct 1178 ms 211980 KB Output is correct
11 Correct 1273 ms 210128 KB Output is correct
12 Correct 2047 ms 199568 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 210344 KB Output is correct
2 Correct 2087 ms 212852 KB Output is correct
3 Correct 2122 ms 212876 KB Output is correct
4 Correct 1481 ms 210284 KB Output is correct
5 Correct 1310 ms 210936 KB Output is correct
6 Correct 1092 ms 198776 KB Output is correct
7 Correct 1997 ms 212752 KB Output is correct
8 Correct 1966 ms 212700 KB Output is correct
9 Correct 1764 ms 212608 KB Output is correct
10 Correct 1178 ms 211980 KB Output is correct
11 Correct 1273 ms 210128 KB Output is correct
12 Correct 2047 ms 199568 KB Output is correct
13 Correct 1787 ms 223164 KB Output is correct
14 Correct 2016 ms 221064 KB Output is correct
15 Correct 2173 ms 212760 KB Output is correct
16 Correct 1254 ms 215792 KB Output is correct
17 Correct 1082 ms 216548 KB Output is correct
18 Correct 1146 ms 198980 KB Output is correct
19 Correct 1821 ms 223148 KB Output is correct
20 Correct 1911 ms 221732 KB Output is correct
21 Correct 1653 ms 223256 KB Output is correct
22 Correct 1171 ms 212040 KB Output is correct
23 Correct 1470 ms 209944 KB Output is correct
24 Correct 2059 ms 199436 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75468 KB Output is correct
2 Correct 46 ms 75464 KB Output is correct
3 Correct 50 ms 75408 KB Output is correct
4 Incorrect 52 ms 75528 KB Output isn't correct
5 Halted 0 ms 0 KB -