제출 #1167173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167173		Zero_OP	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	305 ms	25428 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 2e5 + 5;

int N, Q;
vi group_by_radius[MAX];
vpi queries[MAX];
int ans[MAX];

struct FenwickTree{
      vi bit;
      FenwickTree(int n) : bit(n + 1, 0) {}

      void update(int id, int val){
            for(; id < sz(bit); id += id & (-id)) bit[id] += val;
      }

      int query(int id){
            int sum = 0;
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

      int query(int l, int r){
            return query(r) - query(l-1);
      }

      int walk(int sum){ //find first position that prefix sum > sum
            int pos = 0;
            for(int i = 31 - __builtin_clz(sz(bit)-1); i >= 0; --i){
                  if(pos + (1 << i) < sz(bit) && sum >= bit[pos + (1 << i)]){
                        sum -= bit[pos + (1 << i)];
                        pos += (1 << i);
                  }
            }
//            cout << dbg(pos) << '\n';
            return pos+1;
      }
};

struct doll{
      int r, h;
} dolls[MAX];

int main(){
      setIO();

      cin >> N >> Q;
      vi radius, height;
      FOR(i, 0, N) {
            cin >> dolls[i].r >> dolls[i].h;
            radius.pb(dolls[i].r);
            height.pb(dolls[i].h);
      }

      sort(all(radius)); compact(radius);
      sort(all(height)); compact(height);

      FOR(i, 0, N){
//            if(dolls[i].r >= 4 && dolls[i].h <= 19){
//                  cout << dolls[i].r << ' ' << dolls[i].h << '\n';
//            }
            int r = lower_bound(all(radius), dolls[i].r) - radius.begin();
            int h = lower_bound(all(height), dolls[i].h) - height.begin() + 1;
            group_by_radius[r].pb(h);

      }

      FOR(i, 0, Q){
            int A, B;
            cin >> A >> B;

            A = lower_bound(all(radius), A) - radius.begin();
            if(A == N){
                  ans[i] = 0;
                  continue;
            }

            B = upper_bound(all(height), B) - height.begin();
            if(B == 0){
                  ans[i] = 0;
                  continue;
            }

            queries[A].pb(mp(i, B));
      }

//      cout << "visiting order\n";
      FenwickTree tr(sz(height));

      ROF(i, sz(radius), 0){
            vi delay;
            sort(all(group_by_radius[i]));
            for(auto h : group_by_radius[i]){
                  int match = tr.walk(tr.query(h));
//                  cout << dbg(match) << '\n';
                  if(match == sz(height)+1){
//                        cout << "ADfadas\n";
                        break;
                  }

//                  cout << dbg(radius[i]) << dbg(height[h]) << dbg(height[match]) << '\n';
                  tr.update(match, -1);
            }

            for(auto h : group_by_radius[i]) {
                  tr.update(h, +1);
//                  cout << radius[i] << ' ' << height[h] << '\n';
            }


            for(auto [id, h] : queries[i]){
                  ans[id] = tr.query(h);
            }
      }
//      cout << '\n';

      FOR(i, 0, Q){
            cout << ans[i] << '\n';
      }

      return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49