oj.uz

Submission #998220

# Submission time Handle Problem Language Result Execution time Memory
998220 2024-06-13T12:06:16 Z cowwycow Examination (JOI19_examination) C++14
0 / 100
 471 ms 27196 KB 
#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

struct node {
  int x, y, z, i, val;
};

const int maxn = 1e6 + 5;

struct BIT {
	int b[maxn], n;

	void build(int _n) {
		n = _n;
		fill(b, b + n + 1, 0);
	}
	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;

vector<node> v;
int n, q, ans[maxn];

void cdq(int l, int r) {
	if(l == r) return;
	int m = (l + r) / 2;
	cdq(l, m); cdq(m + 1, r);

	int a = l, b = m + 1, sum = 0;
	vector<pair<int, int>> record;
	vector<node> tmp;
	while(a <= m && b <= r){
		if(v[a].y >= v[b].y){
			int add = v[a].val;
			bit.update(v[a].z, add), sum += add, record.push_back({v[a].z, add}), tmp.push_back(v[a]);
			a++;
		}else{
			ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
			b++;
		}
	}
	while(a <= m){
		tmp.push_back(v[a]);
		a++;
	}
	while(b <= r){
		ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
		b++;
	}
	for(int i = l; i <= r; i++){
		v[i] = tmp[i - l];
	}
	for(auto i : record) bit.update(i.first, -i.second);
}	

bool comp(node a, node b){
	if(a.x == b.x && a.y == b.y){
		if(a.val == b.val){
			return a.z < b.z;
		}
		return a.val > b.val;
	}
	return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x);
}

map<int, int> mp;

void solve() {
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b;
		c = a + b;
		mp[a] = true;
		mp[b] = true;
		mp[c] = true;
		v.push_back({a, b, c, i, 1});
	}
	for(int i = n; i < n + q; i++){
		int x, y, z;
		cin >> x >> y >> z;
		mp[x] = true;
		mp[y] = true;
		mp[z] = true;
		v.push_back({x, y, z, i, 0});
	}
	int id = 1;
	for(auto i : mp){
		mp[i.first] = id;
		id++;
	}
	for(int i = 0; i < v.size(); i++){
		v[i].x = mp[v[i].x];
		v[i].y = mp[v[i].y];
		v[i].z = mp[v[i].z];
	}
	bit.build(id);
	sort(v.begin(), v.end(), comp);
	cdq(0, n + q - 1);
	for(int i = n; i < n + q; i++) cout << ans[i] << '\n';
}

int main() {
	file();
	solve();
}

Compilation message

examination.cpp: In function 'void solve()':
examination.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
examination.cpp: In function 'void file()':
examination.cpp:9:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   freopen(name".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 12 ms 3728 KB Output is correct
8 Correct 12 ms 3652 KB Output is correct
9 Correct 12 ms 3720 KB Output is correct
10 Correct 9 ms 3388 KB Output is correct
11 Incorrect 8 ms 3388 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 471 ms 27196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 471 ms 27196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 12 ms 3728 KB Output is correct
8 Correct 12 ms 3652 KB Output is correct
9 Correct 12 ms 3720 KB Output is correct
10 Correct 9 ms 3388 KB Output is correct
11 Incorrect 8 ms 3388 KB Output isn't correct
12 Halted 0 ms 0 KB -