Submission #386164

#	Time	Username	Problem	Language	Result	Execution time	Memory
386164		jeroenodb	Examination (JOI19_examination)	C++14	100 / 100	528 ms	19772 KiB

examination

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {  for (const T &x : v) os << x << '\n'; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 2e9+2;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
struct event {
    int x,y,c,i=-1;
    bool operator<(const event& o) const {
        return c > o.c or (c== o.c and i < o.i);
    }
};
struct event2 {
    int x,y,i=-1;
    bool operator<(const event2& o) const {
        return x> o.x or (x==o.x and i<o.i);
    }
};
int main() {
    int n,q; cin >> n >> q;


    vector<event> events(n);
    vector<event2> events2(n);
    vector<pair<int,int>> points;
    for(int i=0;i<n;++i) {
        auto& e = events[i];
        cin >> e.x >> e.y;
        e.c = e.x+e.y;
        events2[i] = {e.x,e.y,-1};
    }
    vi ans(q);
    for(int i=0;i<q;++i) {
        auto& e = events[i];
        int a,b,c;
        cin >> a >> b >> c;
        if(c < a+b) {
            events2.push_back({a,b,i});
        } else {
            events.push_back({a,b,c,i});
        }
    }
    sort(all(events));
    ordered_multiset sx,sy;
    for(auto& e: events) {
        if(e.i==-1) {
            // point insertion
            sx.insert(e.x);
            sy.insert(e.y);
        } else {
            // debug(sx); debug(sy);
            ans[e.i] -= sx.order_of_key(e.x);
            ans[e.i] += sy.size()-sy.order_of_key(e.y);
        }
    }
    sort(all(events2));
    sy.clear();
    for(auto& e: events2) {
        if(e.i==-1) {
            sy.insert(e.y);
        } else {
            ans[e.i] = sy.size()-sy.order_of_key(e.y);
        }
    }
    cout << ans;
    

}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:43:15: warning: unused variable 'e' [-Wunused-variable]
   43 |         auto& e = events[i];
      |               ^

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57