oj.uz

Submission #808807

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

#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace __gnu_pbds;
using namespace std;

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 ) {
        if ( l > pos || r < pos )
            return;

        segTree[v].insert( val );
        int mid = (r - l) / 2 + l;

        if ( l == r )
            return;

        update( v * 2 + 1, l, mid, pos, val );
        update( v * 2 + 2, mid + 1, r, pos, val );
    }

    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 );

        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] );
        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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 55 ms 18940 KB Output is correct
8 Correct 65 ms 18840 KB Output is correct
9 Correct 61 ms 18936 KB Output is correct
10 Incorrect 41 ms 17192 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 206928 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 3088 ms 206928 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 1 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 55 ms 18940 KB Output is correct
8 Correct 65 ms 18840 KB Output is correct
9 Correct 61 ms 18936 KB Output is correct
10 Incorrect 41 ms 17192 KB Output isn't correct
11 Halted 0 ms 0 KB -