Submission #808957

#	Time	Username	Problem	Language	Result	Execution time	Memory
808957		LucaIlie	Examination (JOI19_examination)	C++17	100 / 100	2511 ms	257824 KiB

examination

#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 x[MAX_N], y[MAX_N], z[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;
map<int, int> normX, normY;

signed main() {
    int n, q;

    cin >> n >> q;
    for ( int i = 0; i < n; i++ ) {
        cin >> x[i] >> y[i];
        z[i] = x[i] + y[i];
    }
    for ( int i = 0; i < q; i++ )
        cin >> a[i] >> b[i] >> c[i];

    for ( int i = 0; i < n; i++ )
        updates[z[i]].push_back( i ), vals.push_back( z[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 i = 0; i < n; i++ )
        normX[x[i]] = 1, normY[y[i]] = 1;
    for ( int i = 0; i < q; i++ )
        normX[a[i]] = 1, normY[b[i]] = 1;
    int valX = 0;
    for ( auto p: normX )
        normX[p.first] = valX++;
    int valY = 0;
    for ( auto p: normY )
        normY[p.first] = valY++;
    for ( int i = 0; i < n; i++ ) {
        x[i] = normX[x[i]];
        y[i] = normY[y[i]];
    }
    for ( int i = 0; i < n; i++ ) {
        a[i] = normX[a[i]];
        b[i] = normY[b[i]];
    }

    for ( int val: vals ) {
        for ( int i: updates[val] )
            bambam.update( 0, 0, MAX_VAL, x[i], y[i], i );
        for ( int i: queries[val] )
            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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57