Submission #257211

#	Time	Username	Problem	Language	Result	Execution time	Memory
257211		infinitepro	Examination (JOI19_examination)	C++17	100 / 100	2775 ms	166148 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_updat

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

typedef tree<ii,null_type,less<ii>,rb_tree_tag,
tree_order_statistics_node_update> ost;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

class LazyTree{
  //Here    ↓
    int N; vector<ost> st;
    int gpt;
  //Here                                        ↓
    void upd(int v, int l, int r, int L, int R, int d){
        if(r < L or R < l) return;
        // add d into sorted array
        st[v].insert({d, gpt});
        if(l == r) return;

        int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
        upd(v1, l, m, L, R, d);
        upd(v2, m+1, r, L, R, d);
        return;
    }
  //↓ Here
    int qry(int v, int l, int r, int L, int R, int d){
        if(r < L or R < l) return 0;
        if(L <= l and r <= R){
            int cfvs = st[v].size() - st[v].order_of_key({d, 0});
            return cfvs;
        }
        int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
     //Here                      ↓
        return qry(v1, l, m, L, R, d)+qry(v2, m+1, r, L, R, d);
    }
    public:
        LazyTree(int N){st.resize(4*N);this->N = N; gpt = 0;}
      //Here                   ↓
        void upd(int L, int R, int d){gpt++; return upd(1, 0, N, L, R, d);}
      //↓ Here
        int qry(int L, int R, int d){return qry(1, 0, N, L, R, d);}
};

struct node1{
    int s, t;
};

struct node2{
    int a, b, c, idx;
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin >> n >> q;
    vector<node1> a(n);
    for(auto &i : a) cin >> i.s >> i.t;
    sort(all(a), [](auto a, auto b){return a.s+a.t>b.s+b.t;});

    vector<node2> cpq(q);
    for(int x = 0; x < q; x++){
        cin >> cpq[x].a >> cpq[x].b >> cpq[x].c;
        cpq[x].idx = x;
    }
    sort(all(cpq), [](auto z1, auto z2){return z1.c>z2.c;});

    ost ccrow; int jvc = 1;
    for(int x = 0; x < n; x++){
        ccrow.insert({a[x].s, jvc++});
    }

    int jp = ccrow.size()+20;
    LazyTree ST(jp);

    vi sol(q); int stp = 0;
    for(auto qq : cpq){
        while(stp < n && a[stp].s+a[stp].t >= qq.c){
            // insert into merge segtree
            int xv = ccrow.order_of_key({a[stp].s, 0});
            ST.upd(xv, xv, a[stp].t);
            stp++;
        }

        int xv = ccrow.order_of_key({qq.a, 0});
        sol[qq.idx] = ST.qry(xv, jp, qq.b);
    }

    for(auto i : sol) cout << i << endl;


    return 0;
}

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