Submission #1293270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293270		denilb	Examination (JOI19_examination)	C++20	0 / 100	1099 ms	139016 KiB

examination

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fastio ios::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr), cin.exceptions(cin.failbit);
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-9
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define drep(i, a, b) for(int i = (b-1); i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define X first
#define Y second
#define vc vector
typedef string str;
typedef long long ll;
typedef unsigned int UI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<double,double> pdd;
typedef tuple<int,int,int> tii;
typedef pair<ll,ll> plli;
typedef vc<int> vi;
typedef vc<vi> vvi;
typedef vc<vvi> vvvi;
typedef vc<ll> vlli;
typedef vc<vlli> vvlli;
typedef vc<pii> vpii;
typedef vc<vpii> vvpii;
typedef vc<plli> vplli;
typedef vc<tii> vtii;
typedef vc<str> vs;
typedef vc<vs> vvs;
typedef vc<double> vd;
typedef vc<vd> vvd;
typedef vc<vvd> vvvd;

template<typename A, typename B> istream& operator>>(istream& in, pair<A,B>& p) {return in >> p.first >> p.second;}

#define INLINE   inline __attribute__ ((always_inline))
#define NOINLINE __attribute__ ((noinline))
#define DB(...) do { cerr << __VA_ARGS__ << endl; } while (0)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A,B>& p) {os << "(" << p.first << "," << p.second << ")";return os;}
template<typename A, typename B, typename C> ostream& operator<<(ostream &os, const tuple<A,B,C>& t) {os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T>& v) {os << "{";rep(i,0,sz(v)) {if (i) os << ", "; os << v[i];}os << "}";return os;}
template<typename T> ostream& operator<<(ostream &os, const set<T>& s) {vector<T> vs(all(s));os << vs;return os;}
template<typename T> string i2s(T x) { ostringstream o; o << x; return o.str(); }
vs splt(string s, char c = ' ') {vs all; int p = 0, np;while ((np = (int)s.find(c, p)) >= 0) {if (np != p) all.pb(s.substr(p, np - p));p = np + 1;}if (p < sz(s)) all.pb(s.substr(p));return all;}

#define ARGS_SIZE_(a1,a2,a3,a4,a5,a6,a7,a8,a9,size,...) size
#define ARGS_SIZE(...) ARGS_SIZE_(__VA_ARGS__,9,8,7,6,5,4,3,2,1)

#define DB_1(x) #x << "=" << (x) <<
#define DB_2(x, ...) #x << "=" << (x) << ", " << DB_1(__VA_ARGS__)
#define DB_3(x, ...) #x << "=" << (x) << ", " << DB_2(__VA_ARGS__)
#define DB_4(x, ...) #x << "=" << (x) << ", " << DB_3(__VA_ARGS__)
#define DB_5(x, ...) #x << "=" << (x) << ", " << DB_4(__VA_ARGS__)
#define DB_6(x, ...) #x << "=" << (x) << ", " << DB_5(__VA_ARGS__)
#define DB_7(x, ...) #x << "=" << (x) << ", " << DB_6(__VA_ARGS__)
#define DB_8(x, ...) #x << "=" << (x) << ", " << DB_7(__VA_ARGS__)
#define DB_9(x, ...) #x << "=" << (x) << ", " << DB_8(__VA_ARGS__)
#define DB__(size, ...) DB_##size(__VA_ARGS__)
#define DB_(size, ...) DB__(size, __VA_ARGS__)
#define DBV(...) do { cerr << DB_(ARGS_SIZE(__VA_ARGS__), __VA_ARGS__) endl; } while (0)
 
// ---------- END OF TEMPLATE ----------

template <typename T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/**
 * Author:
 * Description:
 * Usage: indexed_set<pii> s;
 *  s.insert({x[i], i});
 *  s.erase({x[i-k], i-k});
 *  s.find_by_order((k-1)/2)->first;
 *  s.order_of_key(7)
 * Time: $O(\log N)$
 */

const int N = 1<<17;
indexed_set<pii> t[2*N];
int n;

void add(int p, int value) {
    for (t[p += n].insert({value, p}); p > 1; p >>= 1) t[p>>1].insert({value, p});
}

int query(int l, int r, int c) {
    int res = 0;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1){
            res += sz(t[l]) - t[l].order_of_key({c, -1});
            l++;
        }
        if(r&1){
            r--;
            res += sz(t[r]) - t[r].order_of_key({c, -1});
        }
    }
    return res;
}

int main(){
    int s, q;
    cin >> s >> q;
    vpii student(s);
    vpii a2i;
    set<int> bb;
    for(int i=0; i<s; i++){
        int a, b;
        cin >> a >> b;
        student[i] = {a, b};
        a2i.eb(a, i);
        bb.insert(b);
    }
    n = sz(bb);
    map<int,int> b2i;
    int e = 0;
    for(auto it=bb.begin(); it!=bb.end(); it++, e++){
        b2i[*it] = e;
    }
    assert(e == n);
    vtii qry(q);
    for(int i=0; i<q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        qry[i] = {a, b, c};
        a2i.eb(a, ~i);
    }
    sort(a2i.rbegin(), a2i.rend());
    vi ans(q);
    for(auto[a, i]: a2i){
        if(i < 0){
            i = ~i;
            auto[a, b, c] = qry[i];
            auto it = b2i.lower_bound(b);
            if(it == b2i.end()) continue;
            ans[i] = query(it->second, n, c);
        } else {
            auto[a,b] = student[i];
            add(b2i[b], a+b);
        }
    }
    for(int x: ans) cout << x << endl;
}

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