Submission #1088783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088783		coldbr3w	Examination (JOI19_examination)	C++17	100 / 100	319 ms	48396 KiB

examination

#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
 
#define int long long
const long long inf = 1e18+1;
const int mod = 1e9+7;
const int MAXN = 3e6+100;
 
struct BIT {
  int b[MAXN], n;
 
  void init(int _n) {
    n = _n;
    for(int i = 0 ; i <= n ; ++i) b[i] = 0;
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  int query(int x) {
    int ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
} bit;
struct Pt{
	int x , y , z , i , t;	
};
Pt a[MAXN];
int ans[MAXN];
void cdq(int l , int r){
	if(l == r) return ;
	int mid = l + r >> 1;
	cdq(l , mid) ; cdq(mid+1 , r);
	int i = l, j = mid+1 ,sum = 0;
	vector<int> record;
	vector<Pt> tmp;
	while(i <= mid && j <= r){
		if(a[i].y > a[j].y) {
			if(a[i].t == 0) bit.update(a[i].z , 1) , sum ++ , record.push_back(a[i].z);
			tmp.push_back(a[i++]);
		}
		else{
			ans[a[j].i] += sum - bit.query(a[j].z);
			tmp.push_back(a[j++]);
		}
	}
	while(i <= mid) tmp.push_back(a[i++]);
	while(j <= r) ans[a[j].i] += sum - bit.query(a[j].z), tmp.push_back(a[j++]);
	for(int i = l ; i <= r ; i++) a[i] = tmp[i-l];
	for(auto i : record) bit.update(i , -1);
	vector<int> ().swap(record);
  	vector<Pt> ().swap(tmp);
}
map<int , int> mp;
int32_t main(){
  	//freopen("KNIGHTGAME.inp", "r", stdin);
	//freopen("KNIGHTGAME.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	int n , q; cin >> n >> q;
	vector<int> comp;
	for(int i = 1 ; i <= n ; i++) cin >> a[i].x >> a[i].y, a[i].i = i , a[i].z = a[i].x + a[i].y, a[i].t = 0 , comp.push_back(a[i].z);
	for(int j = 1 ; j <= q ; j ++){
		int x , y , z; cin>> x >> y >> z;
		a[n + j] = {x-1 , y-1 , z-1 , n + j , 1};
		comp.push_back(z-1);
	}
	sort(all(comp));
	comp.erase(unique(comp.begin() , comp.end()) , comp.end());
	for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
	for(int i = 1 ; i <= n + q ; i++) a[i].z = mp[a[i].z];
	
	sort(a+1, a+n+q+1, [&](auto a, auto b) { 
      return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x); 
  	}); 
	bit.init(n + q);
	cdq(1 , n + q);
	for(int i = 1 ; i <= q ; i++) cout << ans[i + n] << "\n";
 
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void cdq(long long int, long long int)':
examination.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid = l + r >> 1;
      |            ~~^~~
examination.cpp: In function 'int32_t main()':
examination.cpp:77:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
      |                  ~~^~~~~~~~~~~~~

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