oj.uz

Submission #1088783

# Submission time Handle Problem Language Result Execution time Memory
1088783 2024-09-15T04:34:07 Z coldbr3w Examination (JOI19_examination) C++17
100 / 100
 319 ms 48396 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 1768 KB Output is correct
8 Correct 6 ms 1816 KB Output is correct
9 Correct 7 ms 1816 KB Output is correct
10 Correct 6 ms 1816 KB Output is correct
11 Correct 5 ms 1816 KB Output is correct
12 Correct 3 ms 1396 KB Output is correct
13 Correct 5 ms 1652 KB Output is correct
14 Correct 5 ms 1560 KB Output is correct
15 Correct 6 ms 1560 KB Output is correct
16 Correct 4 ms 1544 KB Output is correct
17 Correct 7 ms 1816 KB Output is correct
18 Correct 3 ms 1396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 37928 KB Output is correct
2 Correct 239 ms 38052 KB Output is correct
3 Correct 244 ms 38044 KB Output is correct
4 Correct 223 ms 36788 KB Output is correct
5 Correct 184 ms 36620 KB Output is correct
6 Correct 143 ms 31904 KB Output is correct
7 Correct 222 ms 38040 KB Output is correct
8 Correct 222 ms 38072 KB Output is correct
9 Correct 225 ms 37888 KB Output is correct
10 Correct 167 ms 36772 KB Output is correct
11 Correct 195 ms 36776 KB Output is correct
12 Correct 112 ms 32084 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 37928 KB Output is correct
2 Correct 239 ms 38052 KB Output is correct
3 Correct 244 ms 38044 KB Output is correct
4 Correct 223 ms 36788 KB Output is correct
5 Correct 184 ms 36620 KB Output is correct
6 Correct 143 ms 31904 KB Output is correct
7 Correct 222 ms 38040 KB Output is correct
8 Correct 222 ms 38072 KB Output is correct
9 Correct 225 ms 37888 KB Output is correct
10 Correct 167 ms 36772 KB Output is correct
11 Correct 195 ms 36776 KB Output is correct
12 Correct 112 ms 32084 KB Output is correct
13 Correct 281 ms 41632 KB Output is correct
14 Correct 274 ms 40852 KB Output is correct
15 Correct 234 ms 38048 KB Output is correct
16 Correct 286 ms 38548 KB Output is correct
17 Correct 230 ms 38816 KB Output is correct
18 Correct 150 ms 31908 KB Output is correct
19 Correct 296 ms 41732 KB Output is correct
20 Correct 282 ms 41112 KB Output is correct
21 Correct 280 ms 41628 KB Output is correct
22 Correct 172 ms 36992 KB Output is correct
23 Correct 199 ms 36764 KB Output is correct
24 Correct 120 ms 31912 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 1768 KB Output is correct
8 Correct 6 ms 1816 KB Output is correct
9 Correct 7 ms 1816 KB Output is correct
10 Correct 6 ms 1816 KB Output is correct
11 Correct 5 ms 1816 KB Output is correct
12 Correct 3 ms 1396 KB Output is correct
13 Correct 5 ms 1652 KB Output is correct
14 Correct 5 ms 1560 KB Output is correct
15 Correct 6 ms 1560 KB Output is correct
16 Correct 4 ms 1544 KB Output is correct
17 Correct 7 ms 1816 KB Output is correct
18 Correct 3 ms 1396 KB Output is correct
19 Correct 265 ms 37928 KB Output is correct
20 Correct 239 ms 38052 KB Output is correct
21 Correct 244 ms 38044 KB Output is correct
22 Correct 223 ms 36788 KB Output is correct
23 Correct 184 ms 36620 KB Output is correct
24 Correct 143 ms 31904 KB Output is correct
25 Correct 222 ms 38040 KB Output is correct
26 Correct 222 ms 38072 KB Output is correct
27 Correct 225 ms 37888 KB Output is correct
28 Correct 167 ms 36772 KB Output is correct
29 Correct 195 ms 36776 KB Output is correct
30 Correct 112 ms 32084 KB Output is correct
31 Correct 281 ms 41632 KB Output is correct
32 Correct 274 ms 40852 KB Output is correct
33 Correct 234 ms 38048 KB Output is correct
34 Correct 286 ms 38548 KB Output is correct
35 Correct 230 ms 38816 KB Output is correct
36 Correct 150 ms 31908 KB Output is correct
37 Correct 296 ms 41732 KB Output is correct
38 Correct 282 ms 41112 KB Output is correct
39 Correct 280 ms 41628 KB Output is correct
40 Correct 172 ms 36992 KB Output is correct
41 Correct 199 ms 36764 KB Output is correct
42 Correct 120 ms 31912 KB Output is correct
43 Correct 319 ms 48396 KB Output is correct
44 Correct 312 ms 48300 KB Output is correct
45 Correct 315 ms 48228 KB Output is correct
46 Correct 288 ms 46832 KB Output is correct
47 Correct 266 ms 46860 KB Output is correct
48 Correct 139 ms 32168 KB Output is correct
49 Correct 300 ms 48176 KB Output is correct
50 Correct 309 ms 48344 KB Output is correct
51 Correct 299 ms 48052 KB Output is correct
52 Correct 254 ms 46840 KB Output is correct
53 Correct 206 ms 39808 KB Output is correct