Submission #1059120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059120		arnavsrivastava0123	Examination (JOI19_examination)	C++17	2 / 100	3062 ms	41804 KiB

examination

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
#define F first
#define S second
 
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = 1e5;
const int INF = 1e9;

struct Node{
  ordered_set<int> s;
};

vector<Node> t(4 * MAXN);

Node merge(Node &left, Node &right){
    ordered_set<int> st;
    if(left.s.size() < right.s.size()){
      st = left.s;
      for(int p: right.s) st.insert(p);
    }else{
      st = right.s;
      for(int p: left.s) st.insert(p);
    }
    return Node{st};
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v].s.insert(new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r, int C) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        int x = t[v].s.size();
        return x - t[v].s.order_of_key(C);
    }
    int tm = (tl + tr) / 2;
    return query(v*2, tl, tm, l, min(r, tm), C) + query(v*2+1, tm+1, tr, max(l, tm+1), r, C);
}

struct Query{
  int X, Y, Z, idx;

  bool operator<(Query other) const
    {
        return Y > other.Y;
    }
};
 
void solve(){
   int n, q; cin >> n >> q;
   vector<pair<int, int>> s(n);
   for(int i = 0; i < n;i++){
      cin >> s[i].F >> s[i].S;
   }
   sort(all(s));
   vector<pair<int, int>> b;
   for(int i = 0; i < n;i++){
      b.pb({s[i].S, i});
   }
   sort(b.rbegin(), b.rend());
   vector<int> ans(q);
   vector<Query> qr;
   for(int i = 0; i < q;i++){
      int X, Y, Z; cin >> X >> Y >> Z;
      qr.pb({X, Y, Z, i});
   }
   sort(all(qr));
   for(int i = 0, j = 0; i < q;i++){
      while(j < n && b[j].F >= qr[i].Y){
        update(1, 0, n - 1, b[j].S, b[j].F + s[b[j].S].F);
        j++;
      }
      int l = lower_bound(all(s), mp(qr[i].X, -INF)) - s.begin();
      ans[qr[i].idx] = query(1, 0, n - 1, l, n - 1, qr[i].Z);
   }
   for(int i = 0; i < q;i++){
      cout << ans[i] << '\n';
   }
   
}
 
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
 
int T = 1; //cin >> T;
while(T--){
  solve();
}
}
/*
segtree with ordered set as nodes
use this to query for C
we need to order the queries
largest B to smallest B
so that we can update efficiently
then binary search for range
works but too slow
*/

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