oj.uz

Submission #808847

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

#define int long long

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 SEG_TREE {
    unordered_map<long long , ordered_set> segTree;

    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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 53 ms 18932 KB Output is correct
8 Correct 65 ms 18896 KB Output is correct
9 Correct 55 ms 18908 KB Output is correct
10 Correct 57 ms 18952 KB Output is correct
11 Correct 32 ms 7744 KB Output is correct
12 Correct 26 ms 6572 KB Output is correct
13 Correct 66 ms 18508 KB Output is correct
14 Correct 57 ms 18520 KB Output is correct
15 Correct 61 ms 18448 KB Output is correct
16 Correct 29 ms 7192 KB Output is correct
17 Correct 57 ms 20316 KB Output is correct
18 Correct 83 ms 6596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 244616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 244616 KB Time limit exceeded
2 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 53 ms 18932 KB Output is correct
8 Correct 65 ms 18896 KB Output is correct
9 Correct 55 ms 18908 KB Output is correct
10 Correct 57 ms 18952 KB Output is correct
11 Correct 32 ms 7744 KB Output is correct
12 Correct 26 ms 6572 KB Output is correct
13 Correct 66 ms 18508 KB Output is correct
14 Correct 57 ms 18520 KB Output is correct
15 Correct 61 ms 18448 KB Output is correct
16 Correct 29 ms 7192 KB Output is correct
17 Correct 57 ms 20316 KB Output is correct
18 Correct 83 ms 6596 KB Output is correct
19 Execution timed out 3080 ms 244616 KB Time limit exceeded
20 Halted 0 ms 0 KB -