Submission #839412

#	Time	Username	Problem	Language	Result	Execution time	Memory
839412		huutuan	Examination (JOI19_examination)	C++14	2 / 100	3081 ms	324552 KiB

examination

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct nigga{
   int x, y, z, i;
   nigga(int a=0, int b=0, int c=0, int d=0): x(a), y(b), z(c), i(d){}
   bool operator<(const nigga &a) const {
      return make_pair(-z, i)<make_pair(-a.z, a.i);
   }
};


struct FenwickTree{
   int n;
   unordered_map<int, unordered_map<int, int>> t;

   void init(int _n){
      n=_n;
   }

   void update(int x, int y, int val){
      for (int i=x; i<=n; i+=i&(-i))
         for (int j=y; j<=n; j+=j&(-j)) t[i][j]+=val;
   }

   int get(int x, int y){
      int ans=0;
      for (int i=x; i; i-=i&(-i))
         for (int j=y; j; j-=j&(-j)) ans+=t[i][j];
      return ans;
   }
} bit;

const int N=2e5+1;
int n, q, ans[N];
nigga a[N];

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> q;
   vector<int> r, c;
   for (int i=1; i<=n; ++i) cin >> a[i].x >> a[i].y, a[i].z=a[i].x+a[i].y, r.push_back(a[i].x), c.push_back(a[i].y), a[i].i=i;
   for (int i=n+1; i<=n+q; ++i) cin >> a[i].x >> a[i].y >> a[i].z, r.push_back(a[i].x), c.push_back(a[i].y), a[i].i=i;
   sort(all(r)); sort(all(c)); r.resize(unique(all(r))-r.begin()); c.resize(unique(all(c))-c.begin());
   for (int i=1; i<=n+q; ++i) a[i].x=lower_bound(all(r), a[i].x)-r.begin()+1, a[i].y=lower_bound(all(c), a[i].y)-c.begin()+1;
   sort(a+1, a+n+q+1);
   bit.init(N-1);
   int cnt=0;
   for (int i=1; i<=n+q; ++i){
      if (a[i].i<=n) bit.update(a[i].x, a[i].y, 1), ++cnt;
      else ans[a[i].i-n]=cnt-(bit.get(a[i].x-1, bit.n)+bit.get(bit.n, a[i].y-1)-bit.get(a[i].x-1, a[i].y-1));
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

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