제출 #808860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
808860		LucaIlie	Examination (JOI19_examination)	C++17	2 / 100	3087 ms	242572 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 = 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 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57