Submission #839438

#	Time	Username	Problem	Language	Result	Execution time	Memory
839438		huutuan	Examination (JOI19_examination)	C++14	100 / 100	487 ms	61320 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);
   }
};

const int N=2e5+1;
int n, q, ans[N];
nigga a[N];
vector<int> node[N];
vector<int> t[N];

void fake_update(int x, int y){
   for (int i=x; i<N; i+=i&-i) node[i].push_back(y);
}

void update(int x, int y){
   for (int i=x; i<N; i+=i&-i)
      for (int j=lower_bound(all(node[i]), y)-node[i].begin()+1; j<=sz(node[i]); j+=j&-j) ++t[i][j];
}

int get(int x, int y){
   int res=0;
   for (int i=x; i; i-=i&-i)
      for (int j=upper_bound(all(node[i]), y)-node[i].begin(); j; j-=j&-j) res+=t[i][j];
   return res;
}

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].x*=-1, a[i].y*=-1, 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, a[i].x*=-1, a[i].y*=-1, a[i].z*=-1, 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;
   for (int i=1; i<=n; ++i) fake_update(a[i].x, a[i].y);
   sort(a+1, a+n+q+1);
   for (int i=1; i<N; ++i){
      node[i].push_back(-1);
      node[i].push_back(1e9);
      sort(all(node[i]));
      node[i].resize(unique(all(node[i]))-node[i].begin());
      t[i].resize(sz(node[i])+1);
   }
   for (int i=1; i<=n+q; ++i){
      if (a[i].i<=n) update(a[i].x, a[i].y);
      else ans[a[i].i-n]=get(a[i].x, a[i].y);
   }
   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: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57