oj.uz

Submission #997940

# Submission time Handle Problem Language Result Execution time Memory
997940 2024-06-13T07:02:01 Z Tozzyyyy Examination (JOI19_examination) C++14
0 / 100
 278 ms 52096 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;	
};
struct cmp{
	bool operator() (Pt a , Pt b){
      return (a.x == b.x ? (a.y == b.y ? a.z > b.z : a.y > b.y) : a.x > b.x);	
	}
};
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;
map<Pt , int , cmp> cnt;
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 , cnt[{a[i].x , a[i].y , a[i].z , 1 , 0}]++, comp.push_back(a[i].z);
	for(int j = 1 ; j <= q ; j ++){
		int x , y , z; cin>> x >> y >> z;
		Pt t = {x , y , z , 1 , 0};
		ans[n + j];
		a[n + j] = {x , y , z , n + j , 1};
		comp.push_back(z);
	}
	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[n + i] << "\n";	
	}
 
	return 0;
}

Compilation message

examination.cpp: In function 'void cdq(long long int, long long int)':
examination.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int mid = l + r >> 1;
      |            ~~^~~
examination.cpp: In function 'int32_t main()':
examination.cpp:79:12: warning: statement has no effect [-Wunused-value]
   79 |   ans[n + j];
      |   ~~~~~~~~~^
examination.cpp:78:6: warning: unused variable 't' [-Wunused-variable]
   78 |   Pt t = {x , y , z , 1 , 0};
      |      ^
examination.cpp:85: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]
   85 |  for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4560 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 7 ms 5744 KB Output is correct
8 Correct 7 ms 5724 KB Output is correct
9 Correct 7 ms 5744 KB Output is correct
10 Correct 7 ms 5744 KB Output is correct
11 Correct 7 ms 5832 KB Output is correct
12 Incorrect 4 ms 5080 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 50980 KB Output is correct
2 Correct 278 ms 52096 KB Output is correct
3 Correct 266 ms 50632 KB Output is correct
4 Correct 263 ms 50228 KB Output is correct
5 Correct 244 ms 50072 KB Output is correct
6 Incorrect 172 ms 36596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 50980 KB Output is correct
2 Correct 278 ms 52096 KB Output is correct
3 Correct 266 ms 50632 KB Output is correct
4 Correct 263 ms 50228 KB Output is correct
5 Correct 244 ms 50072 KB Output is correct
6 Incorrect 172 ms 36596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4560 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 7 ms 5744 KB Output is correct
8 Correct 7 ms 5724 KB Output is correct
9 Correct 7 ms 5744 KB Output is correct
10 Correct 7 ms 5744 KB Output is correct
11 Correct 7 ms 5832 KB Output is correct
12 Incorrect 4 ms 5080 KB Output isn't correct
13 Halted 0 ms 0 KB -